]>
Commit | Line | Data |
---|---|---|
b4e1e09c MH |
1 | /* -*- linux-c -*- |
2 | * Map Functions | |
1b276fc2 | 3 | * Copyright (C) 2005, 2006, 2007 Red Hat Inc. |
b4e1e09c MH |
4 | * |
5 | * This file is part of systemtap, and is free software. You can | |
6 | * redistribute it and/or modify it under the terms of the GNU General | |
7 | * Public License (GPL); either version 2, or (at your option) any | |
8 | * later version. | |
9 | */ | |
10 | ||
11 | #ifndef _MAP_C_ | |
e32551b1 MH |
12 | #define _MAP_C_ |
13 | ||
b9c556e4 MH |
14 | /** @file map.c |
15 | * @brief Implements maps (associative arrays) and lists | |
16 | */ | |
17 | ||
55a163fc | 18 | #include "sym.c" |
549b9c3b MH |
19 | #include "stat-common.c" |
20 | #include "map-stat.c" | |
e32551b1 | 21 | |
204b456c | 22 | static int map_sizes[] = { |
43614f5d MH |
23 | sizeof(int64_t), |
24 | MAP_STRING_LENGTH, | |
25 | sizeof(stat), | |
26 | 0 | |
204b456c MH |
27 | }; |
28 | ||
43614f5d MH |
29 | unsigned int int64_hash (const int64_t v) |
30 | { | |
31 | return (unsigned int)hash_long ((unsigned long)v, HASH_TABLE_BITS); | |
32 | } | |
33 | ||
34 | int int64_eq_p (int64_t key1, int64_t key2) | |
35 | { | |
36 | return key1 == key2; | |
37 | } | |
43614f5d | 38 | |
43614f5d MH |
39 | void str_copy(char *dest, char *src) |
40 | { | |
3c2a749a MH |
41 | int len = 0; |
42 | if (src) { | |
43 | len = strlen(src); | |
44 | if (len > MAP_STRING_LENGTH - 1) | |
45 | len = MAP_STRING_LENGTH - 1; | |
46 | memcpy (dest, src, len); | |
47 | } | |
43614f5d MH |
48 | dest[len] = 0; |
49 | } | |
43614f5d | 50 | |
66f95fac MH |
51 | void str_add(void *dest, char *val) |
52 | { | |
53 | char *dst = (char *)dest; | |
54 | int len = strlen(val); | |
55 | int len1 = strlen(dst); | |
56 | int num = MAP_STRING_LENGTH - 1 - len1; | |
57 | ||
58 | if (len > num) | |
59 | len = num; | |
cf0c46c2 | 60 | memcpy (&dst[len1], val, len); |
66f95fac MH |
61 | dst[len + len1] = 0; |
62 | } | |
63 | ||
43614f5d MH |
64 | int str_eq_p (char *key1, char *key2) |
65 | { | |
66 | return strncmp(key1, key2, MAP_STRING_LENGTH - 1) == 0; | |
67 | } | |
68 | ||
69 | unsigned int str_hash(const char *key1) | |
204b456c MH |
70 | { |
71 | int hash = 0, count = 0; | |
72 | char *v1 = (char *)key1; | |
204b456c MH |
73 | while (*v1 && count++ < 5) { |
74 | hash += *v1++; | |
75 | } | |
43614f5d | 76 | return (unsigned int)hash_long((unsigned long)hash, HASH_TABLE_BITS); |
204b456c MH |
77 | } |
78 | ||
e5d2abb5 MH |
79 | /** @addtogroup maps |
80 | * Implements maps (associative arrays) and lists | |
81 | * @{ | |
82 | */ | |
83 | ||
84 | /** Return an int64 from a map node. | |
85 | * This function will return the int64 value of a map_node | |
86 | * from a map containing int64s. You can get the map_nodes in a map | |
87 | * with _stp_map_start(), _stp_map_iter() and foreach(). | |
88 | * @param m pointer to the map_node. | |
89 | * @returns an int64 value. | |
90 | */ | |
43614f5d | 91 | int64_t _stp_get_int64(struct map_node *m) |
204b456c | 92 | { |
063b69fe MH |
93 | if (!m || m->map->type != INT64) |
94 | return 0; | |
43614f5d | 95 | return *(int64_t *)((long)m + m->map->data_offset); |
204b456c MH |
96 | } |
97 | ||
e5d2abb5 MH |
98 | /** Return a string from a map node. |
99 | * This function will return the string value of a map_node | |
100 | * from a map containing strings. You can get the map_nodes in a map | |
101 | * with _stp_map_start(), _stp_map_iter() and foreach(). | |
102 | * @param m pointer to the map_node. | |
103 | * @returns a pointer to a string. | |
104 | */ | |
43614f5d MH |
105 | char *_stp_get_str(struct map_node *m) |
106 | { | |
063b69fe MH |
107 | if (!m || m->map->type != STRING) |
108 | return "bad type"; | |
43614f5d MH |
109 | return (char *)((long)m + m->map->data_offset); |
110 | } | |
111 | ||
e5d2abb5 MH |
112 | /** Return a stat pointer from a map node. |
113 | * This function will return the stats of a map_node | |
114 | * from a map containing stats. You can get the map_nodes in a map | |
115 | * with _stp_map_start(), _stp_map_iter() and foreach(). | |
116 | * @param m pointer to the map_node. | |
117 | * @returns A pointer to the stats. | |
118 | */ | |
43614f5d MH |
119 | stat *_stp_get_stat(struct map_node *m) |
120 | { | |
063b69fe MH |
121 | if (!m || m->map->type != STAT) |
122 | return 0; | |
43614f5d MH |
123 | return (stat *)((long)m + m->map->data_offset); |
124 | } | |
125 | ||
e5d2abb5 MH |
126 | /** Return an int64 key from a map node. |
127 | * This function will return an int64 key from a map_node. | |
05785c11 | 128 | * @param mn pointer to the map_node. |
e5d2abb5 MH |
129 | * @param n key number |
130 | * @returns an int64 | |
131 | * @sa key1int(), key2int() | |
132 | */ | |
133 | int64_t _stp_key_get_int64 (struct map_node *mn, int n) | |
134 | { | |
063b69fe MH |
135 | int type; |
136 | int64_t res = 0; | |
137 | ||
138 | if (mn) { | |
139 | res = (*mn->map->get_key)(mn, n, &type).val; | |
063b69fe MH |
140 | if (type != INT64) |
141 | res = 0; | |
142 | } | |
143 | return res; | |
e5d2abb5 | 144 | } |
43614f5d | 145 | |
e5d2abb5 MH |
146 | /** Return a string key from a map node. |
147 | * This function will return an string key from a map_node. | |
05785c11 | 148 | * @param mn pointer to the map_node. |
e5d2abb5 MH |
149 | * @param n key number |
150 | * @returns a pointer to a string | |
151 | * @sa key1str(), key2str() | |
e32551b1 | 152 | */ |
e5d2abb5 MH |
153 | char *_stp_key_get_str (struct map_node *mn, int n) |
154 | { | |
063b69fe MH |
155 | int type; |
156 | char *str = ""; | |
157 | ||
158 | if (mn) { | |
159 | str = (*mn->map->get_key)(mn, n, &type).strp; | |
063b69fe MH |
160 | if (type != STRING) |
161 | str = "bad type"; | |
162 | } | |
163 | return str; | |
e5d2abb5 | 164 | } |
e32551b1 | 165 | |
7ba70af1 MH |
166 | |
167 | ||
204b456c MH |
168 | /** Create a new map. |
169 | * Maps must be created at module initialization time. | |
170 | * @param max_entries The maximum number of entries allowed. Currently that number will | |
171 | * be preallocated. If more entries are required, the oldest ones will be deleted. This makes | |
172 | * it effectively a circular buffer. If max_entries is 0, there will be no maximum and entries | |
173 | * will be allocated dynamically. | |
174 | * @param type Type of values stored in this map. | |
175 | * @return A MAP on success or NULL on failure. | |
e5d2abb5 | 176 | * @ingroup map_create |
204b456c MH |
177 | */ |
178 | ||
7ba70af1 | 179 | static int _stp_map_init(MAP m, unsigned max_entries, int type, int key_size, int data_size, int cpu) |
204b456c | 180 | { |
43614f5d | 181 | int size; |
204b456c | 182 | |
204b456c MH |
183 | m->maxnum = max_entries; |
184 | m->type = type; | |
185 | if (type >= END) { | |
7ba70af1 MH |
186 | _stp_error("unknown map type %d\n", type); |
187 | return -1; | |
204b456c | 188 | } |
204b456c | 189 | if (max_entries) { |
ee8d9a0d | 190 | unsigned i; |
132c23b4 | 191 | void *tmp; |
43614f5d MH |
192 | |
193 | /* size is the size of the map_node. */ | |
194 | /* add space for the value. */ | |
195 | key_size = ALIGN(key_size,4); | |
196 | m->data_offset = key_size; | |
197 | if (data_size == 0) | |
198 | data_size = map_sizes[type]; | |
199 | data_size = ALIGN(data_size,4); | |
200 | size = key_size + data_size; | |
7ba70af1 | 201 | |
7ba70af1 | 202 | |
953c5ad1 MH |
203 | for (i = 0; i < max_entries; i++) { |
204 | if (cpu < 0) | |
68c2e2a3 | 205 | tmp = _stp_kmalloc(size); |
953c5ad1 | 206 | else |
68c2e2a3 | 207 | tmp = _stp_kmalloc_node(size, cpu_to_node(cpu)); |
953c5ad1 | 208 | |
132c23b4 | 209 | if (!tmp) |
4b670dde | 210 | return -1; |
953c5ad1 | 211 | |
8c235ce5 | 212 | // dbug ("allocated %lx\n", (long)tmp); |
953c5ad1 MH |
213 | list_add((struct list_head *)tmp, &m->pool); |
214 | ((struct map_node *)tmp)->map = m; | |
204b456c | 215 | } |
204b456c | 216 | } |
43614f5d | 217 | if (type == STAT) |
7ba70af1 MH |
218 | m->hist.type = HIST_NONE; |
219 | return 0; | |
132c23b4 | 220 | } |
7ba70af1 MH |
221 | |
222 | ||
223 | static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size) | |
224 | { | |
4b670dde | 225 | MAP m = (MAP) _stp_kzalloc(sizeof(struct map_root)); |
7ba70af1 MH |
226 | if (m == NULL) |
227 | return NULL; | |
953c5ad1 | 228 | |
953c5ad1 MH |
229 | INIT_LIST_HEAD(&m->pool); |
230 | INIT_LIST_HEAD(&m->head); | |
7ba70af1 | 231 | if (_stp_map_init(m, max_entries, type, key_size, data_size, -1)) { |
953c5ad1 | 232 | _stp_map_del(m); |
7ba70af1 MH |
233 | return NULL; |
234 | } | |
204b456c MH |
235 | return m; |
236 | } | |
237 | ||
953c5ad1 | 238 | static PMAP _stp_pmap_new(unsigned max_entries, int type, int key_size, int data_size) |
7ba70af1 | 239 | { |
953c5ad1 | 240 | int i; |
7ba70af1 MH |
241 | MAP map, m; |
242 | ||
4b670dde | 243 | PMAP pmap = (PMAP) _stp_kzalloc(sizeof(struct pmap)); |
953c5ad1 | 244 | if (pmap == NULL) |
7ba70af1 MH |
245 | return NULL; |
246 | ||
68c2e2a3 | 247 | pmap->map = map = (MAP) _stp_alloc_percpu (sizeof(struct map_root)); |
953c5ad1 MH |
248 | if (map == NULL) |
249 | goto err; | |
250 | ||
251 | /* initialize the memory lists first so if allocations fail */ | |
252 | /* at some point, it is easy to clean up. */ | |
253 | for_each_cpu(i) { | |
254 | m = per_cpu_ptr (map, i); | |
255 | INIT_LIST_HEAD(&m->pool); | |
256 | INIT_LIST_HEAD(&m->head); | |
257 | } | |
258 | INIT_LIST_HEAD(&pmap->agg.pool); | |
259 | INIT_LIST_HEAD(&pmap->agg.head); | |
260 | ||
7ba70af1 | 261 | for_each_cpu(i) { |
953c5ad1 | 262 | m = per_cpu_ptr (map, i); |
7ba70af1 | 263 | if (_stp_map_init(m, max_entries, type, key_size, data_size, i)) { |
953c5ad1 | 264 | goto err1; |
7ba70af1 MH |
265 | } |
266 | } | |
267 | ||
953c5ad1 | 268 | if (_stp_map_init(&pmap->agg, max_entries, type, key_size, data_size, -1)) |
7ba70af1 MH |
269 | goto err1; |
270 | ||
953c5ad1 MH |
271 | return pmap; |
272 | ||
7ba70af1 | 273 | err1: |
7ba70af1 | 274 | for_each_cpu(i) { |
953c5ad1 MH |
275 | m = per_cpu_ptr (map, i); |
276 | __stp_map_del(m); | |
7ba70af1 | 277 | } |
68c2e2a3 | 278 | _stp_free_percpu(map); |
953c5ad1 | 279 | err: |
68c2e2a3 | 280 | _stp_kfree(pmap); |
7ba70af1 MH |
281 | return NULL; |
282 | } | |
283 | ||
204b456c MH |
284 | |
285 | /** Get the first element in a map. | |
286 | * @param map | |
287 | * @returns a pointer to the first element. | |
288 | * This is typically used with _stp_map_iter(). See the foreach() macro | |
289 | * for typical usage. It probably does what you want anyway. | |
290 | * @sa foreach | |
291 | */ | |
292 | ||
293 | struct map_node *_stp_map_start(MAP map) | |
294 | { | |
295 | if (map == NULL) | |
296 | return NULL; | |
297 | ||
9a45e491 | 298 | //dbug ("%lx\n", (long)map->head.next); |
204b456c MH |
299 | |
300 | if (list_empty(&map->head)) | |
301 | return NULL; | |
302 | ||
303 | return (struct map_node *)map->head.next; | |
304 | } | |
305 | ||
306 | /** Get the next element in a map. | |
307 | * @param map | |
308 | * @param m a pointer to the current element, returned from _stp_map_start() | |
309 | * or _stp_map_iter(). | |
310 | * @returns a pointer to the next element. | |
311 | * This is typically used with _stp_map_start(). See the foreach() macro | |
312 | * for typical usage. It probably does what you want anyway. | |
313 | * @sa foreach | |
314 | */ | |
315 | ||
316 | struct map_node *_stp_map_iter(MAP map, struct map_node *m) | |
317 | { | |
318 | if (map == NULL) | |
319 | return NULL; | |
320 | ||
204b456c MH |
321 | if (m->lnode.next == &map->head) |
322 | return NULL; | |
323 | ||
324 | return (struct map_node *)m->lnode.next; | |
325 | } | |
326 | ||
89ad3fb0 MH |
327 | /** Clears all the elements in a map. |
328 | * @param map | |
329 | */ | |
330 | ||
331 | void _stp_map_clear(MAP map) | |
332 | { | |
333 | struct map_node *m; | |
334 | ||
335 | if (map == NULL) | |
336 | return; | |
337 | ||
89ad3fb0 MH |
338 | map->num = 0; |
339 | ||
340 | while (!list_empty(&map->head)) { | |
341 | m = (struct map_node *)map->head.next; | |
342 | ||
343 | /* remove node from old hash list */ | |
344 | hlist_del_init(&m->hnode); | |
345 | ||
346 | /* remove from entry list */ | |
347 | list_del(&m->lnode); | |
348 | ||
349 | /* add to free pool */ | |
350 | list_add(&m->lnode, &map->pool); | |
351 | } | |
352 | } | |
353 | ||
c5a2dde1 MH |
354 | void _stp_pmap_clear(PMAP pmap) |
355 | { | |
356 | int i; | |
357 | ||
358 | if (pmap == NULL) | |
359 | return; | |
360 | ||
361 | for_each_cpu(i) { | |
362 | MAP m = per_cpu_ptr (pmap->map, i); | |
4d88dfc7 | 363 | #if NEED_MAP_LOCKS |
c5a2dde1 | 364 | spin_lock(&m->lock); |
4d88dfc7 | 365 | #endif |
c5a2dde1 | 366 | _stp_map_clear(m); |
4d88dfc7 | 367 | #if NEED_MAP_LOCKS |
c5a2dde1 | 368 | spin_unlock(&m->lock); |
4d88dfc7 | 369 | #endif |
c5a2dde1 MH |
370 | } |
371 | _stp_map_clear(&pmap->agg); | |
372 | } | |
953c5ad1 MH |
373 | |
374 | static void __stp_map_del(MAP map) | |
375 | { | |
376 | struct list_head *p, *tmp; | |
377 | ||
378 | /* free unused pool */ | |
379 | list_for_each_safe(p, tmp, &map->pool) { | |
380 | list_del(p); | |
68c2e2a3 | 381 | _stp_kfree(p); |
953c5ad1 MH |
382 | } |
383 | ||
384 | /* free used list */ | |
385 | list_for_each_safe(p, tmp, &map->head) { | |
386 | list_del(p); | |
68c2e2a3 | 387 | _stp_kfree(p); |
953c5ad1 MH |
388 | } |
389 | } | |
390 | ||
204b456c MH |
391 | /** Deletes a map. |
392 | * Deletes a map, freeing all memory in all elements. Normally done only when the module exits. | |
393 | * @param map | |
394 | */ | |
395 | ||
396 | void _stp_map_del(MAP map) | |
397 | { | |
398 | if (map == NULL) | |
399 | return; | |
953c5ad1 MH |
400 | |
401 | __stp_map_del(map); | |
402 | ||
68c2e2a3 | 403 | _stp_kfree(map); |
204b456c MH |
404 | } |
405 | ||
953c5ad1 | 406 | void _stp_pmap_del(PMAP pmap) |
7ba70af1 MH |
407 | { |
408 | int i; | |
7ba70af1 | 409 | |
953c5ad1 | 410 | if (pmap == NULL) |
7ba70af1 MH |
411 | return; |
412 | ||
413 | for_each_cpu(i) { | |
953c5ad1 MH |
414 | MAP m = per_cpu_ptr (pmap->map, i); |
415 | __stp_map_del(m); | |
7ba70af1 | 416 | } |
68c2e2a3 | 417 | _stp_free_percpu(pmap->map); |
7ba70af1 | 418 | |
953c5ad1 MH |
419 | /* free agg map elements */ |
420 | __stp_map_del(&pmap->agg); | |
421 | ||
68c2e2a3 | 422 | _stp_kfree(pmap); |
7ba70af1 MH |
423 | } |
424 | ||
9262e814 MH |
425 | /* sort keynum values */ |
426 | #define SORT_COUNT -5 | |
427 | #define SORT_SUM -4 | |
428 | #define SORT_MIN -3 | |
429 | #define SORT_MAX -2 | |
430 | #define SORT_AVG -1 | |
431 | ||
4a61d600 MH |
432 | /* comparison function for sorts. */ |
433 | static int _stp_cmp (struct list_head *a, struct list_head *b, int keynum, int dir, int type) | |
434 | { | |
435 | struct map_node *m1 = (struct map_node *)a; | |
436 | struct map_node *m2 = (struct map_node *)b; | |
437 | if (type == STRING) { | |
438 | int ret; | |
439 | if (keynum) | |
440 | ret = strcmp(_stp_key_get_str(m1, keynum), _stp_key_get_str(m2, keynum)); | |
441 | else | |
442 | ret = strcmp(_stp_get_str(m1), _stp_get_str(m2)); | |
443 | if ((ret < 0 && dir > 0) || (ret > 0 && dir < 0)) | |
444 | ret = 1; | |
445 | else | |
446 | ret = 0; | |
447 | //_stp_log ("comparing %s and %s and returning %d\n", _stp_get_str(m1), _stp_get_str(m2), ret); | |
448 | return ret; | |
449 | } else { | |
450 | int64_t a,b; | |
9262e814 | 451 | if (keynum > 0) { |
4a61d600 MH |
452 | a = _stp_key_get_int64(m1, keynum); |
453 | b = _stp_key_get_int64(m2, keynum); | |
9262e814 MH |
454 | } else if (keynum < 0) { |
455 | stat *sd1 = (stat *)((long)m1 + m1->map->data_offset); | |
456 | stat *sd2 = (stat *)((long)m2 + m2->map->data_offset); | |
457 | switch (keynum) { | |
458 | case SORT_COUNT: | |
459 | a = sd1->count; | |
460 | b = sd2->count; | |
461 | break; | |
462 | case SORT_SUM: | |
463 | a = sd1->sum; | |
464 | b = sd2->sum; | |
465 | break; | |
466 | case SORT_MIN: | |
467 | a = sd1->min; | |
468 | b = sd2->min; | |
469 | break; | |
470 | case SORT_MAX: | |
471 | a = sd1->max; | |
472 | b = sd2->max; | |
473 | break; | |
474 | case SORT_AVG: | |
6099a10f MH |
475 | a = _stp_div64 (NULL, sd1->sum, sd1->count); |
476 | b = _stp_div64 (NULL, sd2->sum, sd2->count); | |
9262e814 MH |
477 | break; |
478 | default: | |
479 | /* should never happen */ | |
480 | a = b = 0; | |
481 | } | |
4a61d600 MH |
482 | } else { |
483 | a = _stp_get_int64(m1); | |
484 | b = _stp_get_int64(m2); | |
485 | } | |
486 | if ((a < b && dir > 0) || (a > b && dir < 0)) | |
487 | return 1; | |
488 | return 0; | |
489 | } | |
490 | } | |
491 | ||
492 | /* swap function for bubble sort */ | |
493 | static inline void _stp_swap (struct list_head *a, struct list_head *b) | |
494 | { | |
495 | a->prev->next = b; | |
496 | b->next->prev = a; | |
497 | a->next = b->next; | |
498 | b->prev = a->prev; | |
499 | a->prev = b; | |
500 | b->next = a; | |
501 | } | |
502 | ||
4a61d600 MH |
503 | |
504 | /** Sort an entire array. | |
505 | * Sorts an entire array using merge sort. | |
506 | * | |
507 | * @param map Map | |
508 | * @param keynum 0 for the value, or a positive number for the key number to sort on. | |
509 | * @param dir Sort Direction. -1 for low-to-high. 1 for high-to-low. | |
510 | * @sa _stp_map_sortn() | |
511 | */ | |
512 | ||
513 | void _stp_map_sort (MAP map, int keynum, int dir) | |
514 | { | |
515 | struct list_head *p, *q, *e, *tail; | |
516 | int nmerges, psize, qsize, i, type, insize = 1; | |
517 | struct list_head *head = &map->head; | |
518 | ||
519 | if (list_empty(head)) | |
520 | return; | |
521 | ||
9262e814 | 522 | if (keynum > 0) |
4a61d600 | 523 | (*map->get_key)((struct map_node *)head->next, keynum, &type); |
9262e814 MH |
524 | else if (keynum < 0) |
525 | type = INT64; | |
4a61d600 MH |
526 | else |
527 | type = ((struct map_node *)head->next)->map->type; | |
528 | ||
529 | do { | |
530 | tail = head; | |
531 | p = head->next; | |
532 | nmerges = 0; | |
533 | ||
534 | while (p) { | |
535 | nmerges++; | |
536 | q = p; | |
537 | psize = 0; | |
538 | for (i = 0; i < insize; i++) { | |
539 | psize++; | |
540 | q = q->next == head ? NULL : q->next; | |
541 | if (!q) | |
542 | break; | |
543 | } | |
544 | ||
545 | qsize = insize; | |
546 | while (psize > 0 || (qsize > 0 && q)) { | |
547 | if (psize && (!qsize || !q || !_stp_cmp(p, q, keynum, dir, type))) { | |
548 | e = p; | |
549 | p = p->next == head ? NULL : p->next; | |
550 | psize--; | |
551 | } else { | |
552 | e = q; | |
553 | q = q->next == head ? NULL : q->next; | |
554 | qsize--; | |
555 | } | |
556 | ||
557 | /* now put 'e' on tail of list and make it our new tail */ | |
558 | list_del(e); | |
559 | list_add(e, tail); | |
560 | tail = e; | |
561 | } | |
562 | p = q; | |
563 | } | |
564 | insize += insize; | |
565 | } while (nmerges > 1); | |
566 | } | |
567 | ||
fbb24b89 MH |
568 | /** Get the top values from an array. |
569 | * Sorts an array such that the start of the array contains the top | |
570 | * or bottom 'n' values. Use this when sorting the entire array | |
571 | * would be too time-consuming and you are only interested in the | |
572 | * highest or lowest values. | |
573 | * | |
574 | * @param map Map | |
575 | * @param n Top (or bottom) number of elements. 0 sorts the entire array. | |
576 | * @param keynum 0 for the value, or a positive number for the key number to sort on. | |
577 | * @param dir Sort Direction. -1 for low-to-high. 1 for high-to-low. | |
578 | * @sa _stp_map_sort() | |
579 | */ | |
580 | void _stp_map_sortn(MAP map, int n, int keynum, int dir) | |
581 | { | |
083384f0 | 582 | if (n == 0 || n > 30) { |
fbb24b89 MH |
583 | _stp_map_sort(map, keynum, dir); |
584 | } else { | |
585 | struct list_head *head = &map->head; | |
586 | struct list_head *c, *a, *last, *tmp; | |
587 | int type, num, swaps = 1; | |
588 | ||
589 | if (list_empty(head)) | |
590 | return; | |
591 | ||
9262e814 | 592 | if (keynum > 0) |
fbb24b89 | 593 | (*map->get_key)((struct map_node *)head->next, keynum, &type); |
9262e814 MH |
594 | else if (keynum < 0) |
595 | type = INT64; | |
fbb24b89 MH |
596 | else |
597 | type = ((struct map_node *)head->next)->map->type; | |
598 | ||
599 | /* start off with a modified bubble sort of the first n elements */ | |
600 | while (swaps) { | |
601 | num = n; | |
602 | swaps = 0; | |
603 | a = head->next; | |
604 | c = a->next->next; | |
605 | while ((a->next != head) && (--num > 0)) { | |
606 | if (_stp_cmp(a, a->next, keynum, dir, type)) { | |
607 | swaps++; | |
608 | _stp_swap(a, a->next); | |
609 | } | |
610 | a = c->prev; | |
611 | c = c->next; | |
612 | } | |
613 | } | |
614 | ||
615 | /* Now use a kind of insertion sort for the rest of the array. */ | |
616 | /* Each element is tested to see if it should be be in the top 'n' */ | |
617 | last = a; | |
618 | a = a->next; | |
619 | while (a != head) { | |
620 | tmp = a->next; | |
621 | c = last; | |
622 | while (c != head && _stp_cmp(c, a, keynum, dir, type)) | |
623 | c = c->prev; | |
624 | if (c != last) { | |
625 | list_del(a); | |
626 | list_add(a, c); | |
627 | last = last->prev; | |
628 | } | |
629 | a = tmp; | |
630 | } | |
631 | } | |
632 | } | |
4a61d600 | 633 | |
55a163fc MH |
634 | static int print_keytype (char *fmt, int type, key_data *kd) |
635 | { | |
9a45e491 | 636 | //dbug ("*fmt = %c\n", *fmt); |
55a163fc MH |
637 | switch (type) { |
638 | case STRING: | |
639 | if (*fmt != 's') | |
640 | return 1; | |
1b276fc2 | 641 | _stp_print (kd->strp); |
55a163fc MH |
642 | break; |
643 | case INT64: | |
644 | if (*fmt == 'x') | |
645 | _stp_printf("%llx", kd->val); | |
646 | else if (*fmt == 'X') | |
647 | _stp_printf("%llX", kd->val); | |
648 | else if (*fmt == 'd') | |
649 | _stp_printf("%lld", kd->val); | |
650 | else if (*fmt == 'p') { | |
651 | #if BITS_PER_LONG == 64 | |
652 | _stp_printf("%016llx", kd->val); | |
653 | #else | |
654 | _stp_printf("%08llx", kd->val); | |
655 | #endif | |
656 | } else if (*fmt == 'P') | |
657 | _stp_symbol_print ((unsigned long)kd->val); | |
658 | else | |
659 | return 1; | |
660 | break; | |
661 | default: | |
662 | return 1; | |
663 | break; | |
664 | } | |
665 | return 0; | |
666 | } | |
43614f5d | 667 | |
55a163fc MH |
668 | static void print_valtype (MAP map, char *fmt, struct map_node *ptr) |
669 | { | |
670 | switch (map->type) { | |
671 | case STRING: | |
672 | if (*fmt == 's') | |
1b276fc2 | 673 | _stp_print (_stp_get_str(ptr)); |
55a163fc MH |
674 | break; |
675 | case INT64: | |
676 | { | |
677 | int64_t val = _stp_get_int64(ptr); | |
678 | if (*fmt == 'x') | |
679 | _stp_printf("%llx", val); | |
680 | else if (*fmt == 'X') | |
681 | _stp_printf("%llX", val); | |
682 | else if (*fmt == 'd') | |
683 | _stp_printf("%lld", val); | |
684 | else if (*fmt == 'p') { | |
685 | #if BITS_PER_LONG == 64 | |
686 | _stp_printf("%016llx", val); | |
687 | #else | |
688 | _stp_printf("%08llx", val); | |
689 | #endif | |
690 | } else if (*fmt == 'P') | |
691 | _stp_symbol_print ((unsigned long)val); | |
692 | break; | |
693 | } | |
55a163fc MH |
694 | case STAT: |
695 | { | |
e5d2abb5 | 696 | stat *sd = _stp_get_stat(ptr); |
7ba70af1 | 697 | _stp_stat_print_valtype (fmt, &map->hist, sd, 0); |
55a163fc MH |
698 | break; |
699 | } | |
55a163fc MH |
700 | default: |
701 | break; | |
702 | } | |
703 | } | |
704 | ||
e5d2abb5 MH |
705 | /** Print a Map. |
706 | * Print a Map using a format string. | |
707 | * | |
708 | * @param map Map | |
709 | * @param fmt @ref format_string | |
710 | */ | |
4a61d600 | 711 | void _stp_map_printn (MAP map, int n, const char *fmt) |
55a163fc MH |
712 | { |
713 | struct map_node *ptr; | |
714 | int type, num; | |
715 | key_data kd; | |
55a163fc | 716 | |
4a61d600 MH |
717 | if (n < 0) |
718 | return; | |
719 | ||
55a163fc MH |
720 | foreach (map, ptr) { |
721 | char *f = (char *)fmt; | |
722 | while (*f) { | |
723 | f = next_fmt (f, &num); | |
724 | if (num) { | |
725 | /* key */ | |
726 | kd = (*map->get_key)(ptr, num, &type); | |
727 | if (type != END) | |
728 | print_keytype (f, type, &kd); | |
729 | } else { | |
730 | /* value */ | |
731 | print_valtype (map, f, ptr); | |
732 | } | |
733 | if (*f) | |
734 | f++; | |
735 | } | |
1b276fc2 | 736 | _stp_print_char ('\n'); |
4a61d600 MH |
737 | if (n && (--n <= 0)) |
738 | break; | |
204b456c | 739 | } |
1b276fc2 | 740 | _stp_print_char ('\n'); |
43614f5d | 741 | _stp_print_flush(); |
204b456c MH |
742 | } |
743 | ||
4a61d600 MH |
744 | /** Print a Map. |
745 | * Print a Map using a format string. | |
746 | * | |
747 | * @param map Map | |
748 | * @param fmt @ref format_string | |
749 | */ | |
750 | #define _stp_map_print(map,fmt) _stp_map_printn(map,0,fmt) | |
751 | ||
953c5ad1 | 752 | void _stp_pmap_printn_cpu (PMAP pmap, int n, const char *fmt, int cpu) |
7ba70af1 | 753 | { |
953c5ad1 | 754 | MAP m = per_cpu_ptr (pmap->map, cpu); |
7ba70af1 MH |
755 | _stp_map_printn (m, n, fmt); |
756 | } | |
757 | ||
51761586 | 758 | static struct map_node *_stp_new_agg(MAP agg, struct hlist_head *ahead, struct map_node *ptr) |
7ba70af1 MH |
759 | { |
760 | struct map_node *aptr; | |
761 | /* copy keys and aggregate */ | |
7ba70af1 MH |
762 | aptr = _new_map_create(agg, ahead); |
763 | if (aptr == NULL) | |
51761586 | 764 | return NULL; |
7ba70af1 MH |
765 | (*agg->copy)(aptr, ptr); |
766 | switch (agg->type) { | |
767 | case INT64: | |
768 | _new_map_set_int64(agg, | |
769 | aptr, | |
770 | *(int64_t *)((long)ptr + ptr->map->data_offset), | |
771 | 0); | |
772 | break; | |
773 | case STRING: | |
774 | _new_map_set_str(agg, | |
775 | aptr, | |
776 | (char *)((long)ptr + ptr->map->data_offset), | |
777 | 0); | |
778 | break; | |
779 | case STAT: { | |
780 | stat *sd1 = (stat *)((long)aptr + agg->data_offset); | |
781 | stat *sd2 = (stat *)((long)ptr + ptr->map->data_offset); | |
782 | Hist st = &agg->hist; | |
783 | sd1->count = sd2->count; | |
784 | sd1->sum = sd2->sum; | |
785 | sd1->min = sd2->min; | |
786 | sd1->max = sd2->max; | |
787 | if (st->type != HIST_NONE) { | |
788 | int j; | |
789 | for (j = 0; j < st->buckets; j++) | |
790 | sd1->histogram[j] = sd2->histogram[j]; | |
791 | } | |
792 | break; | |
793 | } | |
794 | default: | |
795 | _stp_error("Attempted to aggregate map of type %d\n", agg->type); | |
796 | } | |
51761586 | 797 | return aptr; |
7ba70af1 MH |
798 | } |
799 | ||
800 | static void _stp_add_agg(struct map_node *aptr, struct map_node *ptr) | |
801 | { | |
802 | switch (aptr->map->type) { | |
803 | case INT64: | |
804 | _new_map_set_int64(aptr->map, | |
805 | aptr, | |
806 | *(int64_t *)((long)ptr + ptr->map->data_offset), | |
807 | 1); | |
808 | break; | |
809 | case STRING: | |
810 | _new_map_set_str(aptr->map, | |
811 | aptr, | |
812 | (char *)((long)ptr + ptr->map->data_offset), | |
813 | 1); | |
814 | break; | |
815 | case STAT: { | |
816 | stat *sd1 = (stat *)((long)aptr + aptr->map->data_offset); | |
817 | stat *sd2 = (stat *)((long)ptr + ptr->map->data_offset); | |
818 | Hist st = &aptr->map->hist; | |
51761586 MH |
819 | if (sd1->count == 0) { |
820 | sd1->count = sd2->count; | |
7ba70af1 | 821 | sd1->min = sd2->min; |
7ba70af1 | 822 | sd1->max = sd2->max; |
51761586 MH |
823 | sd1->sum = sd2->sum; |
824 | } else { | |
825 | sd1->count += sd2->count; | |
826 | sd1->sum += sd2->sum; | |
827 | if (sd2->min < sd1->min) | |
828 | sd1->min = sd2->min; | |
829 | if (sd2->max > sd1->max) | |
830 | sd1->max = sd2->max; | |
831 | } | |
7ba70af1 MH |
832 | if (st->type != HIST_NONE) { |
833 | int j; | |
834 | for (j = 0; j < st->buckets; j++) | |
835 | sd1->histogram[j] += sd2->histogram[j]; | |
836 | } | |
837 | break; | |
838 | } | |
839 | default: | |
840 | _stp_error("Attempted to aggregate map of type %d\n", aptr->map->type); | |
841 | } | |
842 | } | |
843 | ||
8d948813 MH |
844 | /** Aggregate per-cpu maps. |
845 | * This function aggregates the per-cpu maps into an aggregated | |
846 | * map. A pointer to that aggregated map is returned. | |
847 | * | |
848 | * A write lock must be held on the map during this function. | |
849 | * | |
850 | * @param map A pointer to a pmap. | |
f903d01c | 851 | * @returns a pointer to the aggregated map. Null on failure. |
8d948813 | 852 | */ |
953c5ad1 | 853 | MAP _stp_pmap_agg (PMAP pmap) |
7ba70af1 MH |
854 | { |
855 | int i, hash; | |
856 | MAP m, agg; | |
857 | struct map_node *ptr, *aptr; | |
858 | struct hlist_head *head, *ahead; | |
859 | struct hlist_node *e, *f; | |
860 | ||
953c5ad1 | 861 | agg = &pmap->agg; |
7ba70af1 MH |
862 | |
863 | /* FIXME. we either clear the aggregation map or clear each local map */ | |
864 | /* every time we aggregate. which would be best? */ | |
865 | _stp_map_clear (agg); | |
866 | ||
867 | for_each_cpu(i) { | |
953c5ad1 | 868 | m = per_cpu_ptr (pmap->map, i); |
4d88dfc7 | 869 | #if NEED_MAP_LOCKS |
c5a2dde1 | 870 | spin_lock(&m->lock); |
4d88dfc7 | 871 | #endif |
7ba70af1 MH |
872 | /* walk the hash chains. */ |
873 | for (hash = 0; hash < HASH_TABLE_SIZE; hash++) { | |
874 | head = &m->hashes[hash]; | |
875 | ahead = &agg->hashes[hash]; | |
876 | hlist_for_each(e, head) { | |
877 | int match = 0; | |
878 | ptr = (struct map_node *)((long)e - sizeof(struct list_head)); | |
879 | hlist_for_each(f, ahead) { | |
880 | aptr = (struct map_node *)((long)f - sizeof(struct list_head)); | |
881 | if ((*m->cmp)(ptr, aptr)) { | |
882 | match = 1; | |
883 | break; | |
884 | } | |
885 | } | |
886 | if (match) | |
887 | _stp_add_agg(aptr, ptr); | |
f903d01c MH |
888 | else { |
889 | if (!_stp_new_agg(agg, ahead, ptr)) { | |
4d88dfc7 | 890 | #if NEED_MAP_LOCKS |
f903d01c | 891 | spin_unlock(&m->lock); |
4d88dfc7 | 892 | #endif |
f903d01c MH |
893 | return NULL; |
894 | } | |
895 | } | |
7ba70af1 MH |
896 | } |
897 | } | |
4d88dfc7 | 898 | #if NEED_MAP_LOCKS |
c5a2dde1 | 899 | spin_unlock(&m->lock); |
4d88dfc7 | 900 | #endif |
7ba70af1 | 901 | } |
8d948813 | 902 | return agg; |
7ba70af1 MH |
903 | } |
904 | ||
8d948813 MH |
905 | /** Get the aggregation map for a pmap. |
906 | * This function returns a pointer to the aggregation map. | |
907 | * It does not do any aggregation. | |
908 | * @param map A pointer to a pmap. | |
909 | * @returns a pointer to an aggregated map. | |
910 | * @sa _stp_pmap_agg() | |
911 | */ | |
953c5ad1 | 912 | #define _stp_pmap_get_agg(pmap) (&pmap->agg) |
7ba70af1 | 913 | |
8d948813 MH |
914 | #define _stp_pmap_printn(map,n,fmt) _stp_map_printn (_stp_pmap_agg(map), n, fmt) |
915 | #define _stp_pmap_print(map,fmt) _stp_map_printn(_stp_pmap_agg(map),0,fmt) | |
af5dd76b | 916 | |
7ba70af1 MH |
917 | static void _new_map_clear_node (struct map_node *m) |
918 | { | |
919 | switch (m->map->type) { | |
920 | case INT64: | |
921 | *(int64_t *)((long)m + m->map->data_offset) = 0; | |
922 | break; | |
923 | case STRING: | |
924 | *(char *)((long)m + m->map->data_offset) = 0; | |
925 | break; | |
926 | case STAT: | |
927 | { | |
928 | stat *sd = (stat *)((long)m + m->map->data_offset); | |
929 | Hist st = &m->map->hist; | |
930 | sd->count = 0; | |
931 | if (st->type != HIST_NONE) { | |
932 | int j; | |
933 | for (j = 0; j < st->buckets; j++) | |
934 | sd->histogram[j] = 0; | |
935 | } | |
936 | break; | |
937 | } | |
938 | } | |
939 | } | |
940 | ||
af5dd76b MH |
941 | static struct map_node *_new_map_create (MAP map, struct hlist_head *head) |
942 | { | |
943 | struct map_node *m; | |
af5dd76b MH |
944 | if (list_empty(&map->pool)) { |
945 | if (!map->wrap) { | |
946 | /* ERROR. no space left */ | |
947 | return NULL; | |
948 | } | |
949 | m = (struct map_node *)map->head.next; | |
af5dd76b MH |
950 | hlist_del_init(&m->hnode); |
951 | } else { | |
952 | m = (struct map_node *)map->pool.next; | |
99675700 | 953 | map->num++; |
af5dd76b MH |
954 | } |
955 | list_move_tail(&m->lnode, &map->head); | |
956 | ||
957 | /* add node to new hash list */ | |
958 | hlist_add_head(&m->hnode, head); | |
af5dd76b MH |
959 | return m; |
960 | } | |
961 | ||
962 | static void _new_map_del_node (MAP map, struct map_node *n) | |
963 | { | |
964 | /* remove node from old hash list */ | |
965 | hlist_del_init(&n->hnode); | |
966 | ||
967 | /* remove from entry list */ | |
968 | list_del(&n->lnode); | |
969 | ||
970 | /* add it back to the pool */ | |
971 | list_add(&n->lnode, &map->pool); | |
972 | ||
973 | map->num--; | |
974 | } | |
975 | ||
976 | static int _new_map_set_int64 (MAP map, struct map_node *n, int64_t val, int add) | |
977 | { | |
978 | if (map == NULL || n == NULL) | |
979 | return -2; | |
980 | ||
3c2a749a MH |
981 | if (add) |
982 | *(int64_t *)((long)n + map->data_offset) += val; | |
983 | else | |
984 | *(int64_t *)((long)n + map->data_offset) = val; | |
985 | ||
af5dd76b MH |
986 | return 0; |
987 | } | |
988 | ||
989 | static int _new_map_set_str (MAP map, struct map_node *n, char *val, int add) | |
990 | { | |
991 | if (map == NULL || n == NULL) | |
992 | return -2; | |
993 | ||
3c2a749a MH |
994 | if (add) |
995 | str_add((void *)((long)n + map->data_offset), val); | |
996 | else | |
997 | str_copy((void *)((long)n + map->data_offset), val); | |
998 | ||
af5dd76b MH |
999 | return 0; |
1000 | } | |
1001 | ||
7ba70af1 | 1002 | static int _new_map_set_stat (MAP map, struct map_node *n, int64_t val, int add) |
af5dd76b MH |
1003 | { |
1004 | stat *sd; | |
af5dd76b MH |
1005 | |
1006 | if (map == NULL || n == NULL) | |
1007 | return -2; | |
1008 | ||
af5dd76b | 1009 | sd = (stat *)((long)n + map->data_offset); |
7ba70af1 MH |
1010 | if (!add) { |
1011 | Hist st = &map->hist; | |
1012 | sd->count = 0; | |
1013 | if (st->type != HIST_NONE) { | |
1014 | int j; | |
1015 | for (j = 0; j < st->buckets; j++) | |
af5dd76b MH |
1016 | sd->histogram[j] = 0; |
1017 | } | |
1018 | } | |
7ba70af1 | 1019 | __stp_stat_add (&map->hist, sd, val); |
af5dd76b MH |
1020 | return 0; |
1021 | } | |
1022 | ||
99675700 MH |
1023 | /** Return the number of elements in a map |
1024 | * This function will return the number of active elements | |
1025 | * in a map. | |
1026 | * @param map | |
1027 | * @returns an int | |
1028 | */ | |
1029 | #define _stp_map_size(map) (map->num) | |
1030 | ||
1031 | /** Return the number of elements in a pmap | |
1032 | * This function will return the number of active elements | |
1033 | * in all the per-cpu maps in a pmap. This is a quick sum and is | |
1034 | * not the same as the number of unique elements that would | |
1035 | * be in the aggragated map. | |
1036 | * @param pmap | |
1037 | * @returns an int | |
1038 | */ | |
1039 | int _stp_pmap_size (PMAP pmap) | |
1040 | { | |
1041 | int i, num = 0; | |
1042 | ||
1043 | for_each_cpu(i) { | |
1044 | MAP m = per_cpu_ptr (pmap->map, i); | |
1045 | num += m->num; | |
1046 | } | |
1047 | return num; | |
1048 | } | |
af5dd76b | 1049 | #endif /* _MAP_C_ */ |
204b456c | 1050 |