SystemTap: SystemTap Runtime Library

00001 /* -*- linux-c -*- */
+00002 
+00003 static int map_sizes[] = {
+00004         sizeof(struct map_node_int64),
+00005         sizeof(struct map_node_stat),
+00006         sizeof(struct map_node_str),
+00007         0
+00008 };
+00009 
+00010 static inline unsigned string_hash(const char *key1, const char *key2)
+00011 {
+00012         int hash = 0, count = 0;
+00013         char *v1 = (char *)key1;
+00014         char *v2 = (char *)key2;
+00015         while (*v1 && count++ < 5) {
+00016                 hash += *v1++;
+00017         }
+00018         while (v2 && *v2 && count++ < 5) {
+00019                 hash += *v2++;
+00020         }
+00021         return hash_long((unsigned long)hash, HASH_TABLE_BITS);
+00022 }
+00023 
+00024 static inline unsigned mixed_hash(const char *key1, long key2)
+00025 {
+00026         int hash = 0, count = 0;
+00027         char *v = (char *)key1;
+00028         while (v && *v && count++ < 5)
+00029                 hash += *v++;
+00030         return hash_long((unsigned long)(hash ^ key2), HASH_TABLE_BITS);
+00031 }
+00032 
+00043 MAP _stp_map_new(unsigned max_entries, enum valtype type)
+00044 {
+00045         size_t size;
+00046         MAP m = (MAP) _stp_valloc(sizeof(struct map_root));
+00047         if (m == NULL)
+00048                 return NULL;
+00049 
+00050         INIT_LIST_HEAD(&m->head);
+00051 
+00052         m->maxnum = max_entries;
+00053         m->type = type;
+00054         if (type >= END) {
+00055                 dbug ("map_new: unknown type %d\n", type);
+00056                 return NULL;
+00057         }
+00058 
+00059         if (max_entries) {
+00060                 void *tmp;
+00061                 int i;
+00062                 struct list_head *e;
+00063 
+00064                 INIT_LIST_HEAD(&m->pool);
+00065                 size = map_sizes[type];
+00066                 tmp = _stp_valloc(max_entries * size);
+00067 
+00068                 for (i = max_entries - 1; i >= 0; i--) {
+00069                         e = i * size + tmp;
+00070                         dbug ("e=%lx\n", (long)e);
+00071                         list_add(e, &m->pool);
+00072                 }
+00073                 m->membuf = tmp;
+00074         }
+00075         return m;
+00076 }
+00077 
+00078 static void map_free_strings(MAP map, struct map_node *n)
+00079 {
+00080         struct map_node_str *m = (struct map_node_str *)n;
+00081         dbug ("n = %lx\n", (long)n);
+00082         if (map->type == STRING) {
+00083                 dbug ("val STRING %lx\n", (long)m->str);
+00084                 if (m->str)
+00085                         _stp_free(m->str);
+00086         }
+00087         if (m->n.key1type == STR) {
+00088                 dbug ("key1 STR %lx\n", (long)key1str(m));
+00089                 if (key1str(m))
+00090                         _stp_free(key1str(m));
+00091         }
+00092         if (m->n.key2type == STR) {
+00093                 dbug ("key2 STR %lx\n", (long)key2str(m));
+00094                 if (key2str(m))
+00095                         _stp_free(key2str(m));
+00096         }
+00097 }
+00098 
+00104 void _stp_map_key_del(MAP map)
+00105 {
+00106         struct map_node *m;
+00107 
+00108         dbug ("create=%d key=%lx\n", map->create, (long)map->key);
+00109         if (map == NULL)
+00110                 return;
+00111 
+00112         if (map->create) {
+00113                 map->create = 0;
+00114                 map->key = NULL;
+00115                 return;
+00116         }
+00117 
+00118         if (map->key == NULL)
+00119                 return;
+00120 
+00121         m = (struct map_node *)map->key;
+00122 
+00123         /* remove node from old hash list */
+00124         hlist_del_init(&m->hnode);
+00125 
+00126         /* remove from entry list */
+00127         list_del(&m->lnode);
+00128 
+00129         /* remove any allocated string storage */
+00130         map_free_strings(map, (struct map_node *)map->key);
+00131 
+00132         if (map->maxnum)
+00133                 list_add(&m->lnode, &map->pool);
+00134         else
+00135                 _stp_free(m);
+00136 
+00137         map->key = NULL;
+00138         map->num--;
+00139 }
+00140 
+00149 struct map_node *_stp_map_start(MAP map)
+00150 {
+00151         if (map == NULL)
+00152                 return NULL;
+00153 
+00154         dbug ("%lx\n", (long)map->head.next);
+00155 
+00156         if (list_empty(&map->head))
+00157                 return NULL;
+00158 
+00159         return (struct map_node *)map->head.next;
+00160 }
+00161 
+00172 struct map_node *_stp_map_iter(MAP map, struct map_node *m)
+00173 {
+00174         if (map == NULL)
+00175                 return NULL;
+00176 
+00177         dbug ("%lx next=%lx  prev=%lx  map->head.next=%lx\n", (long)m, (long)m->lnode.next, (long)m->lnode.prev, (long)map->head.next);
+00178 
+00179         if (m->lnode.next == &map->head)
+00180                 return NULL;
+00181 
+00182         return (struct map_node *)m->lnode.next;
+00183 }
+00184 
+00190 void _stp_map_del(MAP map)
+00191 {
+00192         if (map == NULL)
+00193                 return;
+00194 
+00195         if (!list_empty(&map->head)) {
+00196                 struct map_node *ptr = (struct map_node *)map->head.next;
+00197                 while (ptr && ptr != (struct map_node *)&map->head) {
+00198                         map_free_strings(map, ptr);
+00199                         ptr = (struct map_node *)ptr->lnode.next;
+00200                 }
+00201         }
+00202         _stp_vfree(map->membuf);
+00203         _stp_vfree(map);
+00204 }
+00205 
+00206 /**********************  KEY FUNCTIONS *********************/
+00207 
+00208 
+00218 void _stp_map_key_long_long(MAP map, long key1, long key2)
+00219 {
+00220         unsigned hv;
+00221         struct hlist_head *head;
+00222         struct hlist_node *e;
+00223 
+00224         if (map == NULL)
+00225                 return;
+00226 
+00227         hv = hash_long(key1 ^ key2, HASH_TABLE_BITS);
+00228         head = &map->hashes[hv];
+00229 
+00230         dbug ("hash for %ld,%ld is %d\n", key1, key2, hv);
+00231 
+00232         hlist_for_each(e, head) {
+00233                 struct map_node *n =
+00234                         (struct map_node *)((long)e - sizeof(struct hlist_node));
+00235                 dbug ("n =%lx  key=%ld,%ld\n", (long)n, n->key1.val, n->key2.val);
+00236                 if (key1 == n->key1.val && key2 == n->key2.val) {
+00237                         map->key = n;
+00238                         dbug ("saving key %lx\n", (long)map->key);
+00239                         map->create = 0;
+00240                         return;
+00241                 }
+00242         }
+00243 
+00244         map->c_key1.val = key1;
+00245         map->c_key2.val = key2;
+00246         map->c_key1type = LONG;
+00247         map->c_key2type = LONG;
+00248         map->c_keyhead = head;
+00249         map->create = 1;
+00250 }
+00251 
+00261 void _stp_map_key_str_str(MAP map, char *key1, char *key2)
+00262 {
+00263         unsigned hv;
+00264         struct hlist_head *head;
+00265         struct hlist_node *e;
+00266 
+00267         if (map == NULL)
+00268                 return;
+00269 
+00270         if (key1 == NULL) {
+00271                 map->key = NULL;
+00272                 return;
+00273         }
+00274 
+00275         hv = string_hash(key1, key2);
+00276         head = &map->hashes[hv];
+00277 
+00278         dbug ("hash for %s,%s is %d\n", key1, key2, hv);
+00279 
+00280         hlist_for_each(e, head) {
+00281                 struct map_node *n =
+00282                         (struct map_node *)((long)e - sizeof(struct hlist_node));
+00283                 dbug ("e =%lx  key=%s,%s\n", (long)e, n->key1.str,n->key2.str);
+00284                 if (strcmp(key1, n->key1.str) == 0
+00285                     && (key2 == NULL || strcmp(key2, n->key2.str) == 0)) {
+00286                         map->key = n;
+00287                         dbug ("saving key %lx\n", (long)map->key);
+00288                         map->create = 0;
+00289                         return;
+00290                 }
+00291         }
+00292 
+00293         map->c_key1.str = key1;
+00294         map->c_key2.str = key2;
+00295         map->c_key1type = STR;
+00296         map->c_key2type = STR;
+00297         map->c_keyhead = head;
+00298         map->create = 1;
+00299 }
+00300 
+00310 void _stp_map_key_str_long(MAP map, char *key1, long key2)
+00311 {
+00312         unsigned hv;
+00313         struct hlist_head *head;
+00314         struct hlist_node *e;
+00315 
+00316         if (map == NULL)
+00317                 return;
+00318 
+00319         if (key1 == NULL) {
+00320                 map->key = NULL;
+00321                 return;
+00322         }
+00323 
+00324         hv = mixed_hash(key1, key2);
+00325         head = &map->hashes[hv];
+00326 
+00327         dbug ("hash for %s,%ld is %d\n", key1, key2, hv);
+00328 
+00329         hlist_for_each(e, head) {
+00330                 struct map_node *n =
+00331                         (struct map_node *)((long)e - sizeof(struct hlist_node));
+00332                 dbug ("e =%lx  key=%s,%ld\n", (long)e, n->key1.str,(long)n->key2.val);
+00333                 if (strcmp(key1, n->key1.str) == 0 && key2 == n->key2.val) {
+00334                         map->key = n;
+00335                         dbug ("saving key %lx\n", (long)map->key);
+00336                         map->create = 0;
+00337                         return;
+00338                 }
+00339         }
+00340 
+00341         map->c_key1.str = key1;
+00342         map->c_key2.val = key2;
+00343         map->c_key1type = STR;
+00344         map->c_key2type = LONG;
+00345         map->c_keyhead = head;
+00346         map->create = 1;
+00347 }
+00348 
+00358 void _stp_map_key_long_str(MAP map, long key1, char *key2)
+00359 {
+00360         unsigned hv;
+00361         struct hlist_head *head;
+00362         struct hlist_node *e;
+00363 
+00364         if (map == NULL)
+00365                 return;
+00366 
+00367         hv = mixed_hash(key2, key1);
+00368         head = &map->hashes[hv];
+00369         dbug ("hash for %ld,%s is %d\n", key1, key2, hv);
+00370 
+00371         hlist_for_each(e, head) {
+00372                 struct map_node *n =
+00373                         (struct map_node *)((long)e - sizeof(struct hlist_node));
+00374                 dbug ("e =%lx  key=%ld,%s\n", (long)e, n->key1.val,n->key2.str);
+00375                 if (key1 == n->key1.val && strcmp(key2, n->key2.str) == 0) {
+00376                         map->key = n;
+00377                         dbug ("saving key %lx\n", (long)map->key);
+00378                         map->create = 0;
+00379                         return;
+00380                 }
+00381         }
+00382 
+00383         map->c_key1.val = key1;
+00384         map->c_key2.str = key2;
+00385         map->c_key1type = LONG;
+00386         map->c_key2type = STR;
+00387         map->c_keyhead = head;
+00388         map->create = 1;
+00389 }
+00390 
+00399 void _stp_map_key_str(MAP map, char *key)
+00400 {
+00401         if (map == NULL)
+00402                 return;
+00403         _stp_map_key_str_str(map, key, NULL);
+00404         map->c_key2type = NONE;
+00405 }
+00406 
+00415 void _stp_map_key_long(MAP map, long key)
+00416 {
+00417         if (map == NULL)
+00418                 return;
+00419         _stp_map_key_long_long(map, key, 0);
+00420         map->c_key2type = NONE;
+00421 }
+00422 
+00423 /**********************  SET/GET VALUES *********************/
+00424 
+00425 static void map_copy_keys(MAP map, struct map_node *m)
+00426 {
+00427         m->key1type = map->c_key1type;
+00428         m->key2type = map->c_key2type;
+00429         switch (map->c_key1type) {
+00430         case STR:
+00431                 m->key1.str = _stp_alloc(strlen(map->c_key1.str) + 1);
+00432                 strcpy(m->key1.str, map->c_key1.str);
+00433                 break;
+00434         case LONG:
+00435                 m->key1.val = map->c_key1.val;
+00436                 break;
+00437         case NONE:
+00438                 /* ERROR */
+00439                 break;
+00440         }
+00441         switch (map->c_key2type) {
+00442         case STR:
+00443                 m->key2.str = _stp_alloc(strlen(map->c_key2.str) + 1);
+00444                 strcpy(m->key2.str, map->c_key2.str);
+00445                 break;
+00446         case LONG:
+00447                 m->key2.val = map->c_key2.val;
+00448                 break;
+00449         case NONE:
+00450                 break;
+00451         }
+00452 
+00453         /* add node to new hash list */
+00454         hlist_add_head(&m->hnode, map->c_keyhead);
+00455         
+00456         map->key = m;
+00457         map->create = 0;
+00458         map->num++;
+00459 }
+00460 
+00471 void _stp_map_set_int64(MAP map, int64_t val)
+00472 {
+00473         struct map_node_int64 *m;
+00474 
+00475         if (map == NULL)
+00476                 return;
+00477 
+00478         if (map->create) {
+00479                 if (val == 0)
+00480                         return;
+00481 
+00482                 if (map->maxnum) {
+00483                         if (list_empty(&map->pool)) {
+00484                                 if (map->no_wrap) {
+00485                                         /* ERROR. FIXME */
+00486                                         return;
+00487                                 }
+00488                                 m = (struct map_node_int64 *)map->head.next;
+00489                                 hlist_del_init(&m->n.hnode);
+00490                                 map_free_strings(map, (struct map_node *)m);
+00491                                 dbug ("got %lx off head\n", (long)m);
+00492                         } else {
+00493                                 m = (struct map_node_int64 *)map->pool.next;
+00494                                 dbug ("got %lx off pool\n", (long)m);
+00495                         }
+00496                         list_move_tail(&m->n.lnode, &map->head);
+00497                 } else {
+00498                         m = (struct map_node_int64 *)
+00499                             _stp_calloc(sizeof(struct map_node_int64));
+00500                         /* add node to list */
+00501                         list_add_tail(&m->n.lnode, &map->head);
+00502                 }
+00503 
+00504                 /* copy the key(s) */
+00505                 map_copy_keys(map, &m->n);
+00506 
+00507                 /* set the value */
+00508                 m->val = val;
+00509         } else {
+00510                 if (map->key == NULL)
+00511                         return;
+00512 
+00513                 if (val) {
+00514                         m = (struct map_node_int64 *)map->key;
+00515                         m->val = val;
+00516                 } else {
+00517                         /* setting value to 0 is the same as deleting */
+00518                         _stp_map_key_del(map);
+00519                 }
+00520         }
+00521 }
+00522 
+00528 int64_t _stp_map_get_int64(MAP map)
+00529 {
+00530         struct map_node_int64 *m;
+00531         if (map == NULL || map->create || map->key == NULL)
+00532                 return 0;
+00533         dbug ("%lx\n", (long)map->key);
+00534         m = (struct map_node_int64 *)map->key;
+00535         return m->val;
+00536 }
+00537 
+00548 void _stp_map_set_str(MAP map, char *val)
+00549 {
+00550         struct map_node_str *m;
+00551 
+00552         if (map == NULL)
+00553                 return;
+00554 
+00555         if (map->create) {
+00556                 if (val == NULL)
+00557                         return;
+00558 
+00559                 if (map->maxnum) {
+00560                         if (list_empty(&map->pool)) {
+00561                                 if (map->no_wrap) {
+00562                                         /* ERROR. FIXME */
+00563                                         return;
+00564                                 }
+00565                                 m = (struct map_node_str *)map->head.next;
+00566                                 hlist_del_init(&m->n.hnode);
+00567                                 map_free_strings(map, (struct map_node *)m);
+00568                                 dbug ("got %lx off head\n", (long)m);
+00569                         } else {
+00570                                 m = (struct map_node_str *)map->pool.next;
+00571                                 dbug ("got %lx off pool\n", (long)m);
+00572                         }
+00573                         list_move_tail(&m->n.lnode, &map->head);
+00574                 } else {
+00575                         m = (struct map_node_str *)
+00576                             _stp_calloc(sizeof(struct map_node_str));
+00577                         /* add node to list */
+00578                         list_add_tail(&m->n.lnode, &map->head);
+00579                 }
+00580 
+00581                 /* copy the key(s) */
+00582                 map_copy_keys(map, &m->n);
+00583 
+00584                 /* set the value */
+00585                 m->str = _stp_alloc(strlen(val) + 1);
+00586                 strcpy(m->str, val);
+00587         } else {
+00588                 if (map->key == NULL)
+00589                         return;
+00590 
+00591                 if (val) {
+00592                         m = (struct map_node_str *)map->key;
+00593                         if (m->str)
+00594                                 _stp_free(m->str);
+00595                         m->str = _stp_alloc(strlen(val) + 1);
+00596                         strcpy(m->str, val);
+00597                 } else {
+00598                         /* setting value to 0 is the same as deleting */
+00599                         _stp_map_key_del(map);
+00600                 }
+00601         }
+00602 }
+00603 
+00609 char *_stp_map_get_str(MAP map)
+00610 {
+00611         struct map_node_str *m;
+00612         if (map == NULL || map->create || map->key == NULL)
+00613                 return NULL;
+00614         dbug ("%lx\n", (long)map->key);
+00615         m = (struct map_node_str *)map->key;
+00616         return m->str;
+00617 }
+00618 
+00633 void _stp_map_set_stat(MAP map, stat * stats)
+00634 {
+00635         struct map_node_stat *m;
+00636 
+00637         if (map == NULL)
+00638                 return;
+00639         dbug ("set_stat %lx\n", (long)map->key);
+00640 
+00641         if (map->create) {
+00642                 if (stats == NULL)
+00643                         return;
+00644 
+00645                 if (map->maxnum) {
+00646                         if (list_empty(&map->pool)) {
+00647                                 if (map->no_wrap) {
+00648                                         /* ERROR. FIXME */
+00649                                         return;
+00650                                 }
+00651                                 m = (struct map_node_stat *)map->head.next;
+00652                                 hlist_del_init(&m->n.hnode);
+00653                                 map_free_strings(map, (struct map_node *)m);
+00654                                 dbug ("got %lx off head\n", (long)m);
+00655                         } else {
+00656                                 m = (struct map_node_stat *)map->pool.next;
+00657                                 dbug ("got %lx off pool\n", (long)m);
+00658                         }
+00659                         list_move_tail(&m->n.lnode, &map->head);
+00660                 } else {
+00661                         m = (struct map_node_stat *)
+00662                             _stp_calloc(sizeof(struct map_node_stat));
+00663                         /* add node to list */
+00664                         list_add_tail(&m->n.lnode, &map->head);
+00665                 }
+00666 
+00667                 /* copy the key(s) */
+00668                 map_copy_keys(map, &m->n);
+00669 
+00670                 /* set the value */
+00671                 memcpy(&m->stats, stats, sizeof(stat));
+00672         } else {
+00673                 if (map->key == NULL)
+00674                         return;
+00675 
+00676                 if (stats) {
+00677                         m = (struct map_node_stat *)map->key;
+00678                         memcpy(&m->stats, stats, sizeof(stat));
+00679                 } else {
+00680                         /* setting value to NULL is the same as deleting */
+00681                         _stp_map_key_del(map);
+00682                 }
+00683         }
+00684 }
+00685 
+00692 stat *_stp_map_get_stat(MAP map)
+00693 {
+00694         struct map_node_stat *m;
+00695         if (map == NULL || map->create || map->key == NULL)
+00696                 return NULL;
+00697         dbug ("%lx\n", (long)map->key);
+00698         m = (struct map_node_stat *)map->key;
+00699         return &m->stats;
+00700 }
+00701 
+00713 void _stp_map_stat_add(MAP map, int64_t val)
+00714 {
+00715         struct map_node_stat *m;
+00716         if (map == NULL)
+00717                 return;
+00718 
+00719         if (map->create) {
+00720                 stat st = { 1, val, val, val };
+00721                 /* histogram */
+00722                 _stp_map_set_stat(map, &st);
+00723                 return;
+00724         }
+00725 
+00726         if (map->key == NULL)
+00727                 return;
+00728 
+00729         dbug ("add_stat %lx\n", (long)map->key);
+00730         m = (struct map_node_stat *)map->key;
+00731         m->stats.count++;
+00732         m->stats.sum += val;
+00733         if (val > m->stats.max)
+00734                 m->stats.max = val;
+00735         if (val < m->stats.min)
+00736                 m->stats.min = val;
+00737         /* histogram */
+00738 }
+00739 
+00740 /**********************  List Functions *********************/
+00741 
+00753 MAP _stp_list_new(unsigned max_entries, enum valtype type)
+00754 {
+00755   MAP map = _stp_map_new (max_entries, type);
+00756   map->no_wrap = 1;
+00757   return map;
+00758 }
+00759 
+00765 inline void _stp_list_clear(MAP map)
+00766 {
+00767         if (map == NULL)
+00768                 return;
+00769 
+00770         if (!list_empty(&map->head)) {
+00771                 struct map_node *ptr = (struct map_node *)map->head.next;
+00772 
+00773                 while (ptr && ptr != (struct map_node *)&map->head) {
+00774                         struct map_node *next = (struct map_node *)ptr->lnode.next;
+00775 
+00776                         /* remove node from old hash list */
+00777                         hlist_del_init(&ptr->hnode);
+00778 
+00779                         /* remove from entry list */
+00780                         list_del(&ptr->lnode);
+00781                         
+00782                         /* remove any allocated string storage */
+00783                         map_free_strings(map, ptr);
+00784                         
+00785                         if (map->maxnum)
+00786                                 list_add(&ptr->lnode, &map->pool);
+00787                         else
+00788                                 _stp_free(ptr);
+00789 
+00790                         map->num--;
+00791                         ptr = next;
+00792                 }
+00793         }
+00794 
+00795         if (map->num != 0) {
+00796                 dlog ("ERROR: list is supposed to be empty (has %d)\n", map->num);
+00797         }
+00798 }
+00799 
+00805 inline void _stp_list_add_str(MAP map, char *str)
+00806 {
+00807         _stp_map_key_long(map, map->num);
+00808         _stp_map_set_str(map, str);
+00809 }
+00810 
+00816 inline void _stp_list_add_int64(MAP map, int64_t val)
+00817 {
+00818         _stp_map_key_long(map, map->num);
+00819         _stp_map_set_int64(map, val);
+00820 }
+00821 
+00827 inline int _stp_list_size(MAP map)
+00828 {
+00829         return map->num;
+00830 }
+
map.c
