One Level Up Top Level

runtime/kp_tab.c - ktap

Global variables defined

Data types defined

Functions defined

Macros defined

Source code

  1. /*
  2. * kp_tab.c - Table handling.
  3. *
  4. * This file is part of ktap by Jovi Zhangwei.
  5. *
  6. * Copyright (C) 2012-2013 Jovi Zhangwei <jovi.zhangwei@gmail.com>.
  7. *
  8. * Adapted from luajit and lua interpreter.
  9. * Copyright (C) 2005-2014 Mike Pall.
  10. * Copyright (C) 1994-2008 Lua.org, PUC-Rio.
  11. *
  12. * ktap is free software; you can redistribute it and/or modify it
  13. * under the terms and conditions of the GNU General Public License,
  14. * version 2, as published by the Free Software Foundation.
  15. *
  16. * ktap is distributed in the hope it will be useful, but WITHOUT
  17. * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18. * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  19. * more details.
  20. *
  21. * You should have received a copy of the GNU General Public License along with
  22. * this program; if not, write to the Free Software Foundation, Inc.,
  23. * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
  24. */

  26. #include <linux/spinlock.h>
  27. #include <linux/module.h>
  28. #include <linux/kallsyms.h>
  29. #include <linux/slab.h>
  30. #include <linux/sort.h>
  31. #include "../include/ktap_types.h"
  32. #include "ktap.h"
  33. #include "kp_vm.h"
  34. #include "kp_obj.h"
  35. #include "kp_str.h"
  36. #include "kp_events.h"
  37. #include "kp_tab.h"

  39. ‌#define tab_lock_init(t)                        \
  40.     do {                                \
  41.         (t)->lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;    \
  42.     } while (0)
  43. ‌#define tab_lock(t)                        \
  44.     do {                                \
  45.         local_irq_save(flags);                    \
  46.         arch_spin_lock(&(t)->lock);                \
  47.     } while (0)
  48. ‌#define tab_unlock(t)                        \
  49.     do {                                \
  50.         arch_spin_unlock(&(t)->lock);                \
  51.         local_irq_restore(flags);                \
  52.     } while (0)


  55. ‌const ktap_val_t kp_niltv = { {NULL}, {KTAP_TNIL} } ;
  56. ‌#define niltv  (&kp_niltv)

  58. /* -- Object hashing ------------------------------------------------------ */

  60. /* Hash values are masked with the table hash mask and used as an index. */
  61. static __always_inline
  62. ‌ktap_node_t *hashmask(const ktap_tab_t *t, uint32_t hash)
  63. {
  64.     ktap_node_t *n = t->node;
  65.     return &n[hash & t->hmask];
  66. }

  68. /* String hashes are precomputed when they are interned. */
  69. ‌#define hashstr(t, s)        hashmask(t, (s)->hash)

  71. ‌#define hashlohi(t, lo, hi)    hashmask((t), hashrot((lo), (hi)))
  72. ‌#define hashnum(t, o)        hashlohi((t), (o)->val.n & 0xffffffff, 0)
  73. ‌#define hashgcref(t, o)        hashlohi((t),    \
  74.                 ((unsigned long)(o)->val.gc & 0xffffffff), \
  75.                 ((unsigned long)(o)->val.gc & 0xffffffff) + HASH_BIAS)


  78. /* Hash an arbitrary key and return its anchor position in the hash table. */
  79. ‌static ktap_node_t *hashkey(const ktap_tab_t *t, const ktap_val_t *key)
  80. {
  81.     kp_assert(!tvisint(key));
  82.     if (is_string(key))
  83.         return hashstr(t, rawtsvalue(key));
  84.     else if (is_number(key))
  85.         return hashnum(t, key);
  86.     else if (is_bool(key))
  87.         return hashmask(t, boolvalue(key));
  88.     else
  89.         return hashgcref(t, key);
  90. }

  92. /* -- Table creation and destruction -------------------------------------- */

  94. /* Create new hash part for table. */
  95. static __always_inline
  96. ‌int newhpart(ktap_state_t *ks, ktap_tab_t *t, uint32_t hbits)
  97. {
  98.     uint32_t hsize;
  99.     ktap_node_t *node;
  100.     kp_assert(hbits != 0);

  102.     if (hbits > KP_MAX_HBITS) {
  103.         //kp_error(ks, LJ_ERR_TABOV);
  104.         kp_error(ks, "table overflow\n");
  105.         return -1;
  106.     }
  107.     hsize = 1u << hbits;
  108.     node = vmalloc(hsize * sizeof(ktap_node_t));
  109.     if (!node)
  110.         return -ENOMEM;
  111.     t->freetop = &node[hsize];
  112.     t->node = node;
  113.     t->hmask = hsize-1;

  115.     return 0;
  116. }

  118. /*
  119. * Q: Why all of these copies of t->hmask, t->node etc. to local variables?
  120. * A: Because alias analysis for C is _really_ tough.
  121. *    Even state-of-the-art C compilers won't produce good code without this.
  122. */

  124. /* Clear hash part of table. */
  125. ‌static __always_inline void clearhpart(ktap_tab_t *t)
  126. {
  127.     uint32_t i, hmask = t->hmask;
  128.     ktap_node_t *node = t->node;
  129.     kp_assert(t->hmask != 0);

  131.     for (i = 0; i <= hmask; i++) {
  132.         ktap_node_t *n = &node[i];
  133.         n->next = NULL;
  134.         set_nil(&n->key);
  135.         set_nil(&n->val);
  136.     }

  138.     t->hnum = 0;
  139. }

  141. /* Clear array part of table. */
  142. ‌static __always_inline void clearapart(ktap_tab_t *t)
  143. {
  144.     uint32_t i, asize = t->asize;
  145.     ktap_val_t *array = t->array;
  146.     for (i = 0; i < asize; i++)
  147.         set_nil(&array[i]);
  148. }

  150. /* Create a new table. Note: the slots are not initialized (yet). */
  151. ‌static ktap_tab_t *newtab(ktap_state_t *ks, uint32_t asize, uint32_t hbits)
  152. {
  153.     ktap_tab_t *t;

  155.     t = (ktap_tab_t *)kp_obj_new(ks, sizeof(ktap_tab_t));
  156.     t->gct = ~KTAP_TTAB;
  157.     t->array = NULL;
  158.     t->asize = 0;  /* In case the array allocation fails. */
  159.     t->hmask = 0;

  161.     tab_lock_init(t);

  163.     if (asize > 0) {
  164.         if (asize > KP_MAX_ASIZE) {
  165.             kp_error(ks, "table overflow\n");
  166.             return NULL;
  167.         }

  169.         t->array = vmalloc(asize * sizeof(ktap_val_t));
  170.         if (!t->array)
  171.             return NULL;
  172.         t->asize = asize;
  173.     }
  174.     if (hbits)
  175.         if (newhpart(ks, t, hbits)) {
  176.             vfree(t->array);
  177.             return NULL;
  178.         }
  179.     return t;
  180. }

  182. /* Create a new table.
  183. *
  184. * The array size is non-inclusive. E.g. asize=128 creates array slots
  185. * for 0..127, but not for 128. If you need slots 1..128, pass asize=129
  186. * (slot 0 is wasted in this case).
  187. *
  188. * The hash size is given in hash bits. hbits=0 means no hash part.
  189. * hbits=1 creates 2 hash slots, hbits=2 creates 4 hash slots and so on.
  190. */
  191. ‌ktap_tab_t *kp_tab_new(ktap_state_t *ks, uint32_t asize, uint32_t hbits)
  192. {
  193.     ktap_tab_t *t = newtab(ks, asize, hbits);
  194.     if (!t)
  195.         return NULL;

  197.     clearapart(t);
  198.     if (t->hmask > 0)
  199.         clearhpart(t);
  200.     return t;
  201. }

  203. ‌#define TABLE_NARR_ENTRIES    255 /* PAGE_SIZE / sizeof(ktap_value) - 1 */
  204. ‌#define TABLE_NREC_ENTRIES    2048 /* (PAGE_SIZE * 20) / sizeof(ktap_tnode)*/

  206. ‌ktap_tab_t *kp_tab_new_ah(ktap_state_t *ks, int32_t a, int32_t h)
  207. {
  208.     if (a == 0 && h == 0) {
  209.         a = TABLE_NARR_ENTRIES;
  210.         h = TABLE_NREC_ENTRIES;
  211.     }

  213.     return kp_tab_new(ks, (uint32_t)(a > 0 ? a+1 : 0), hsize2hbits(h));
  214. }

  216. /* Duplicate a table. */
  217. ‌ktap_tab_t *kp_tab_dup(ktap_state_t *ks, const ktap_tab_t *kt)
  218. {
  219.     ktap_tab_t *t;
  220.     uint32_t asize, hmask;
  221.     int i;

  223.     /* allocate default table size */
  224.     t = kp_tab_new_ah(ks, 0, 0);
  225.     if (!t)
  226.         return NULL;

  228.     asize = kt->asize;
  229.     if (asize > 0) {
  230.         ktap_val_t *array = t->array;
  231.         ktap_val_t *karray = kt->array;
  232.         if (asize < 64) {
  233.             /* An inlined loop beats memcpy for < 512 bytes. */
  234.             uint32_t i;
  235.             for (i = 0; i < asize; i++)
  236.                 set_obj(&array[i], &karray[i]);
  237.         } else {
  238.             memcpy(array, karray, asize*sizeof(ktap_val_t));
  239.         }
  240.     }

  242.     hmask = kt->hmask;
  243.     for (i = 0; i <= hmask; i++) {
  244.         ktap_node_t *knode = &kt->node[i];
  245.         if (is_nil(&knode->key))
  246.             continue;
  247.         kp_tab_set(ks, t, &knode->key, &knode->val);
  248.     }
  249.     return t;
  250. }

  252. /* Clear a table. */
  253. ‌void kp_tab_clear(ktap_tab_t *t)
  254. {
  255.     clearapart(t);
  256.     if (t->hmask > 0) {
  257.         ktap_node_t *node = t->node;
  258.         t->freetop = &node[t->hmask+1];
  259.         clearhpart(t);
  260.     }
  261. }

  263. /* Free a table. */
  264. ‌void kp_tab_free(ktap_state_t *ks, ktap_tab_t *t)
  265. {
  266.     if (t->hmask > 0)
  267.         vfree(t->node);
  268.     if (t->asize > 0)
  269.         vfree(t->array);
  270.     kp_free(ks, t);
  271. }

  273. /* -- Table getters ------------------------------------------------------- */

  275. ‌static const ktap_val_t *tab_getinth(ktap_tab_t *t, uint32_t key)
  276. {
  277.     ktap_val_t k;
  278.     ktap_node_t *n;

  280.     set_number(&k, (ktap_number)key);
  281.     n = hashnum(t, &k);
  282.     do {
  283.         if (is_number(&n->key) && nvalue(&n->key) == key) {
  284.             return &n->val;
  285.         }
  286.     } while ((n = n->next));
  287.     return niltv;
  288. }

  290. static __always_inline
  291. ‌const ktap_val_t *tab_getint(ktap_tab_t *t, uint32_t key)
  292. {
  293.     return ((key < t->asize) ? arrayslot(t, key) :
  294.                    tab_getinth(t, key));
  295. }

  297. ‌void kp_tab_getint(ktap_tab_t *t, uint32_t key, ktap_val_t *val)
  298. {
  299.     unsigned long flags;

  301.     tab_lock(t);
  302.     set_obj(val, tab_getint(t, key));
  303.     tab_unlock(t);
  304. }

  306. ‌static const ktap_val_t *tab_getstr(ktap_tab_t *t, ktap_str_t *key)
  307. {
  308.     ktap_node_t *n = hashstr(t, key);
  309.     do {
  310.         if (is_string(&n->key) && rawtsvalue(&n->key) == key)
  311.             return &n->val;
  312.     } while ((n = n->next));
  313.     return niltv;
  314. }

  316. ‌void kp_tab_getstr(ktap_tab_t *t, ktap_str_t *key, ktap_val_t *val)
  317. {
  318.     unsigned long flags;

  320.     tab_lock(t);
  321.     set_obj(val,  tab_getstr(t, key));
  322.     tab_unlock(t);
  323. }

  325. ‌static const ktap_val_t *tab_get(ktap_state_t *ks, ktap_tab_t *t,
  326.                  const ktap_val_t *key)
  327. {
  328.     if (is_string(key)) {
  329.         return tab_getstr(t, rawtsvalue(key));
  330.     } else if (is_number(key)) {
  331.         ktap_number nk = nvalue(key);
  332.         uint32_t k = (uint32_t)nk;
  333.         if (nk == (ktap_number)k) {
  334.             return tab_getint(t, k);
  335.         } else {
  336.             goto genlookup;    /* Else use the generic lookup. */
  337.         }
  338.     } else if (is_eventstr(key)) {
  339.         const ktap_str_t *ts;

  341.         if (!ks->current_event) {
  342.             kp_error(ks,
  343.             "cannot stringify event str in invalid context\n");
  344.             return niltv;
  345.         }

  347.         ts = kp_event_stringify(ks);
  348.         if (!ts)
  349.             return niltv;

  351.         return tab_getstr(t, rawtsvalue(key));
  352.     } else if (!is_nil(key)) {
  353.         ktap_node_t *n;
  354. genlookup:
  355.         n = hashkey(t, key);
  356.         do {
  357.             if (kp_obj_equal(&n->key, key))
  358.                 return &n->val;
  359.         } while ((n = n->next));
  360.     }
  361.     return niltv;
  362. }

  364. ‌void kp_tab_get(ktap_state_t *ks, ktap_tab_t *t, const ktap_val_t *key,
  365.         ktap_val_t *val)
  366. {
  367.     unsigned long flags;

  369.     tab_lock(t);
  370.     set_obj(val, tab_get(ks, t, key));
  371.     tab_unlock(t);
  372. }

  374. /* -- Table setters ------------------------------------------------------- */

  376. /* Insert new key. Use Brent's variation to optimize the chain length. */
  377. ‌static ktap_val_t *kp_tab_newkey(ktap_state_t *ks, ktap_tab_t *t,
  378.                  const ktap_val_t *key)
  379. {
  380.     ktap_node_t *n = hashkey(t, key);

  382.     if (!is_nil(&n->val) || t->hmask == 0) {
  383.         ktap_node_t *nodebase = t->node;
  384.         ktap_node_t *collide, *freenode = t->freetop;

  386.         kp_assert(freenode >= nodebase &&
  387.               freenode <= nodebase+t->hmask+1);
  388.         do {
  389.             if (freenode == nodebase) {  /* No free node found? */
  390.                 //kp_error(ks, LJ_ERR_TABOV);
  391.                 kp_error(ks, "table overflow\n");
  392.                 return NULL;
  393.             }
  394.         } while (!is_nil(&(--freenode)->key));

  396.         t->freetop = freenode;
  397.         collide = hashkey(t, &n->key);
  398.         if (collide != n) {  /* Colliding node not the main node? */
  399.             while (collide->next != n)
  400.                 /* Find predecessor. */
  401.                 collide = collide->next;
  402.             collide->next = freenode;  /* Relink chain. */
  403.              /* Copy colliding node into free node and
  404.              * free main node. */
  405.             freenode->val = n->val;
  406.             freenode->key = n->key;
  407.             freenode->next = n->next;
  408.             n->next = NULL;
  409.             set_nil(&n->val);
  410.             /* Rechain pseudo-resurrected string keys with
  411.              * colliding hashes. */
  412.             while (freenode->next) {
  413.                 ktap_node_t *nn = freenode->next;
  414.                 if (is_string(&nn->key) && !is_nil(&nn->val) &&
  415.                     hashstr(t, rawtsvalue(&nn->key)) == n) {
  416.                     freenode->next = nn->next;
  417.                     nn->next = n->next;
  418.                     n->next = nn;
  419.                 } else {
  420.                     freenode = nn;
  421.                 }
  422.             }
  423.         } else {  /* Otherwise use free node. */
  424.             freenode->next = n->next;  /* Insert into chain. */
  425.             n->next = freenode;
  426.             n = freenode;
  427.         }
  428.     }
  429.     set_obj(&n->key, key);
  430.     t->hnum++;
  431.     return &n->val;
  432. }

  434. ‌static ktap_val_t *tab_setinth(ktap_state_t *ks, ktap_tab_t *t, uint32_t key)
  435. {
  436.     ktap_val_t k;
  437.     ktap_node_t *n;

  439.     set_number(&k, (ktap_number)key);
  440.     n = hashnum(t, &k);
  441.     do {
  442.         if (is_number(&n->key) && nvalue(&n->key) == key)
  443.             return &n->val;
  444.     } while ((n = n->next));
  445.     return kp_tab_newkey(ks, t, &k);
  446. }

  448. static __always_inline
  449. ‌ktap_val_t *tab_setint(ktap_state_t *ks, ktap_tab_t *t, uint32_t key)
  450. {
  451.     return ((key < t->asize) ? arrayslot(t, key) :
  452.                    tab_setinth(ks, t, key));
  453. }

  455. ‌void kp_tab_setint(ktap_state_t *ks, ktap_tab_t *t,
  456.            uint32_t key, const ktap_val_t *val)
  457. {
  458.     ktap_val_t *v;
  459.     unsigned long flags;

  461.     tab_lock(t);
  462.     v = tab_setint(ks, t, key);
  463.     if (likely(v))
  464.         set_obj(v, val);
  465.     tab_unlock(t);
  466. }

  468. ‌void kp_tab_incrint(ktap_state_t *ks, ktap_tab_t *t, uint32_t key,
  469.             ktap_number n)
  470. {
  471.     ktap_val_t *v;
  472.     unsigned long flags;

  474.     tab_lock(t);
  475.     v = tab_setint(ks, t, key);
  476.     if (unlikely(!v))
  477.         goto out;

  479.     if (likely(is_number(v)))
  480.         set_number(v, nvalue(v) + n);
  481.     else if (is_nil(v))
  482.         set_number(v, n);
  483.     else
  484.         kp_error(ks, "use '+=' operator on non-number value\n");

  486. out:
  487.     tab_unlock(t);
  488. }

  490. ‌static ktap_val_t *tab_setstr(ktap_state_t *ks, ktap_tab_t *t,
  491.                   const ktap_str_t *key)
  492. {
  493.     ktap_val_t k;
  494.     ktap_node_t *n = hashstr(t, key);
  495.     do {
  496.         if (is_string(&n->key) && rawtsvalue(&n->key) == key)
  497.             return &n->val;
  498.     } while ((n = n->next));
  499.     set_string(&k, key);
  500.     return kp_tab_newkey(ks, t, &k);
  501. }

  503. ‌void kp_tab_setstr(ktap_state_t *ks, ktap_tab_t *t, const ktap_str_t *key,
  504.            const ktap_val_t *val)
  505. {
  506.     ktap_val_t *v;
  507.     unsigned long flags;

  509.     tab_lock(t);
  510.     v = tab_setstr(ks, t, key);
  511.     if (likely(v))
  512.         set_obj(v, val);
  513.     tab_unlock(t);
  514. }

  516. ‌void kp_tab_incrstr(ktap_state_t *ks, ktap_tab_t *t, const ktap_str_t *key,
  517.             ktap_number n)
  518. {
  519.     ktap_val_t *v;
  520.     unsigned long flags;

  522.     tab_lock(t);
  523.     v = tab_setstr(ks, t, key);
  524.     if (unlikely(!v))
  525.         goto out;

  527.     if (likely(is_number(v)))
  528.         set_number(v, nvalue(v) + n);
  529.     else if (is_nil(v))
  530.         set_number(v, n);
  531.     else
  532.         kp_error(ks, "use '+=' operator on non-number value\n");
  533. out:
  534.     tab_unlock(t);
  535. }

  537. ‌static ktap_val_t *tab_set(ktap_state_t *ks, ktap_tab_t *t,
  538.                const ktap_val_t *key)
  539. {
  540.     ktap_node_t *n;

  542.     if (is_string(key)) {
  543.         return tab_setstr(ks, t, rawtsvalue(key));
  544.     } else if (is_number(key)) {
  545.         ktap_number nk = nvalue(key);
  546.         uint32_t k = (ktap_number)nk;
  547.         if (nk == (ktap_number)k)
  548.             return tab_setint(ks, t, k);
  549.     } else if (itype(key) == KTAP_TKSTACK) {
  550.         /* change stack into string */
  551.         ktap_str_t *bt = kp_obj_kstack2str(ks, key->val.stack.depth,
  552.                                key->val.stack.skip);
  553.         if (!bt)
  554.             return NULL;
  555.         return tab_setstr(ks, t, bt);
  556.     } else if (is_eventstr(key)) {
  557.         const ktap_str_t *ts;

  559.         if (!ks->current_event) {
  560.             kp_error(ks,
  561.             "cannot stringify event str in invalid context\n");
  562.             return NULL;
  563.         }

  565.         ts = kp_event_stringify(ks);
  566.         if (!ts)
  567.             return NULL;

  569.         return tab_setstr(ks, t, ts);
  570.         /* Else use the generic lookup. */
  571.     } else if (is_nil(key)) {
  572.         //kp_error(ks, LJ_ERR_NILIDX);
  573.         kp_error(ks, "table nil index\n");
  574.         return NULL;
  575.     }
  576.     n = hashkey(t, key);
  577.     do {
  578.         if (kp_obj_equal(&n->key, key))
  579.             return &n->val;
  580.     } while ((n = n->next));
  581.     return kp_tab_newkey(ks, t, key);
  582. }

  584. ‌void kp_tab_set(ktap_state_t *ks, ktap_tab_t *t,
  585.         const ktap_val_t *key, const ktap_val_t *val)
  586. {
  587.     ktap_val_t *v;
  588.     unsigned long flags;

  590.     tab_lock(t);
  591.     v = tab_set(ks, t, key);
  592.     if (likely(v))
  593.         set_obj(v, val);
  594.     tab_unlock(t);
  595. }

  597. ‌void kp_tab_incr(ktap_state_t *ks, ktap_tab_t *t, ktap_val_t *key,
  598.          ktap_number n)
  599. {
  600.     ktap_val_t *v;
  601.     unsigned long flags;

  603.     tab_lock(t);
  604.     v = tab_set(ks, t, key);
  605.     if (unlikely(!v))
  606.         goto out;

  608.     if (likely(is_number(v)))
  609.         set_number(v, nvalue(v) + n);
  610.     else if (is_nil(v))
  611.         set_number(v, n);
  612.     else
  613.         kp_error(ks, "use '+=' operator on non-number value\n");
  614. out:
  615.     tab_unlock(t);
  616. }


  619. /* -- Table traversal ----------------------------------------------------- */

  621. /* Get the traversal index of a key. */
  622. ‌static uint32_t keyindex(ktap_state_t *ks, ktap_tab_t *t,
  623.              const ktap_val_t *key)
  624. {
  625.     if (is_number(key)) {
  626.         ktap_number nk = nvalue(key);
  627.         uint32_t k = (uint32_t)nk;
  628.         /* Array key indexes: [0..t->asize-1] */
  629.         if ((uint32_t)k < t->asize && nk == (ktap_number)k)
  630.             return (uint32_t)k;
  631.     }

  633.     if (!is_nil(key)) {
  634.         ktap_node_t *n = hashkey(t, key);
  635.         do {
  636.             if (kp_obj_equal(&n->key, key))
  637.                 return t->asize + (uint32_t)(n - (t->node));
  638.             /* Hash key indexes: [t->asize..t->asize+t->nmask] */
  639.         } while ((n = n->next));
  640.         //kp_err_msg(ks, LJ_ERR_NEXTIDX);
  641.         kp_error(ks, "table next index\n");
  642.         return 0;  /* unreachable */
  643.     }
  644.     return ~0u;  /* A nil key starts the traversal. */
  645. }

  647. /* Advance to the next step in a table traversal. */
  648. ‌int kp_tab_next(ktap_state_t *ks, ktap_tab_t *t, ktap_val_t *key)
  649. {
  650.     unsigned long flags;
  651.     uint32_t i;

  653.     tab_lock(t);
  654.     i = keyindex(ks, t, key);  /* Find predecessor key index. */

  656.     /* First traverse the array keys. */
  657.     for (i++; i < t->asize; i++)
  658.          if (!is_nil(arrayslot(t, i))) {
  659.             set_number(key, i);
  660.             set_obj(key + 1, arrayslot(t, i));
  661.             tab_unlock(t);
  662.             return 1;
  663.         }
  664.     /* Then traverse the hash keys. */
  665.     for (i -= t->asize; i <= t->hmask; i++) {
  666.         ktap_node_t *n = &t->node[i];
  667.         if (!is_nil(&n->val)) {
  668.             set_obj(key, &n->key);
  669.             set_obj(key + 1, &n->val);
  670.             tab_unlock(t);
  671.             return 1;
  672.         }
  673.     }
  674.     tab_unlock(t);
  675.     return 0;  /* End of traversal. */
  676. }

  678. /* -- Table length calculation -------------------------------------------- */

  680. ‌int kp_tab_len(ktap_state_t *ks, ktap_tab_t *t)
  681. {
  682.     unsigned long flags;
  683.     int i, len = 0;

  685.     tab_lock(t);
  686.     for (i = 0; i < t->asize; i++) {
  687.         ktap_val_t *v = &t->array[i];

  689.         if (is_nil(v))
  690.             continue;
  691.         len++;
  692.     }

  694.     for (i = 0; i <= t->hmask; i++) {
  695.         ktap_node_t *n = &t->node[i];

  697.         if (is_nil(&n->key))
  698.             continue;

  700.         len++;
  701.     }
  702.     tab_unlock(t);
  703.     return len;
  704. }

  706. ‌static void string_convert(char *output, const char *input)
  707. {
  708.     if (strlen(input) > 32) {
  709.         strncpy(output, input, 32-4);
  710.         memset(output + 32-4, '.', 3);
  711.     } else
  712.         memcpy(output, input, strlen(input));
  713. }

  715. ‌typedef struct ktap_node2 {
  716.     ktap_val_t key;
  717.     ktap_val_t val;
  718. ‌} ktap_node2_t;

  720. ‌static int hist_record_cmp(const void *i, const void *j)
  721. {
  722.     ktap_number n1 = nvalue(&((const ktap_node2_t *)i)->val);
  723.     ktap_number n2 = nvalue(&((const ktap_node2_t *)j)->val);

  725.     if (n1 == n2)
  726.         return 0;
  727.     else if (n1 < n2)
  728.         return 1;
  729.     else
  730.         return -1;
  731. }

  733. /* todo: make histdump to be faster, just need to sort n entries, not all */

  735. /* print_hist: key should be number/string/ip, value must be number */
  736. ‌static void tab_histdump(ktap_state_t *ks, ktap_tab_t *t, int shownums)
  737. {
  738.     long start_time, delta_time;
  739.     uint32_t i, asize = t->asize;
  740.     ktap_val_t *array = t->array;
  741.     uint32_t hmask = t->hmask;
  742.     ktap_node_t *node = t->node;
  743.     ktap_node2_t *sort_mem;
  744.     char dist_str[39];
  745.     int total = 0, sum = 0;

  747.     start_time = gettimeofday_ns();

  749.     sort_mem = kmalloc((t->asize + t->hnum) * sizeof(ktap_node2_t),
  750.                 GFP_KERNEL);
  751.     if (!sort_mem)
  752.         return;

  754.     /* copy all values in table into sort_mem. */
  755.     for (i = 0; i < asize; i++) {
  756.         ktap_val_t *val = &array[i];
  757.         if (is_nil(val))
  758.             continue;

  760.         if (!is_number(val)) {
  761.             kp_error(ks, "print_hist only can print number\n");
  762.             goto out;
  763.         }

  765.         set_number(&sort_mem[total].key, i);
  766.         set_obj(&sort_mem[total].val, val);
  767.         sum += nvalue(val);
  768.         total++;
  769.     }

  771.     for (i = 0; i <= hmask; i++) {
  772.         ktap_node_t *n = &node[i];
  773.         ktap_val_t *val = &n->val;

  775.         if (is_nil(val))
  776.             continue;

  778.         if (!is_number(val)) {
  779.             kp_error(ks, "print_hist only can print number\n");
  780.             goto out;
  781.         }

  783.         set_obj(&sort_mem[total].key, &n->key);
  784.         set_obj(&sort_mem[total].val, val);
  785.         sum += nvalue(val);
  786.         total++;
  787.     }

  789.     /* sort */
  790.     sort(sort_mem, total, sizeof(ktap_node2_t), hist_record_cmp, NULL);

  792.     dist_str[sizeof(dist_str) - 1] = '\0';

  794.     for (i = 0; i < total; i++) {
  795.         ktap_val_t *key = &sort_mem[i].key;
  796.         ktap_number num = nvalue(&sort_mem[i].val);
  797.         int ratio;

  799.         if (!--shownums)
  800.             break;

  802.         memset(dist_str, ' ', sizeof(dist_str) - 1);
  803.         ratio = (num * (sizeof(dist_str) - 1)) / sum;
  804.         memset(dist_str, '@', ratio);

  806.         if (is_string(key)) {
  807.             //char buf[32] = {0};

  809.             //string_convert(buf, svalue(key));
  810.             if (rawtsvalue(key)->len > 32) {
  811.                 kp_puts(ks, svalue(key));
  812.                 kp_printf(ks, "%s\n%d\n\n", dist_str, num);
  813.             } else {
  814.                 kp_printf(ks, "%31s |%s%-7d\n", svalue(key),
  815.                                 dist_str, num);
  816.             }
  817.         } else if (is_number(key)) {
  818.             kp_printf(ks, "%31d |%s%-7d\n", nvalue(key),
  819.                         dist_str, num);
  820.         } else if (is_kip(key)) {
  821.             char str[KSYM_SYMBOL_LEN];
  822.             char buf[32] = {0};

  824.             SPRINT_SYMBOL(str, nvalue(key));
  825.             string_convert(buf, str);
  826.             kp_printf(ks, "%31s |%s%-7d\n", buf, dist_str, num);
  827.         }
  828.     }

  830.     if (!shownums && total)
  831.         kp_printf(ks, "%31s |\n", "...");

  833. out:
  834.     kfree(sort_mem);

  836.     delta_time = (gettimeofday_ns() - start_time) / NSEC_PER_USEC;
  837.     kp_verbose_printf(ks, "tab_histdump time: %d (us)\n", delta_time);
  838. }

  840. ‌#define DISTRIBUTION_STR "------------- Distribution -------------"
  841. ‌void kp_tab_print_hist(ktap_state_t *ks, ktap_tab_t *t, int n)
  842. {
  843.     kp_printf(ks, "%31s%s%s\n", "value ", DISTRIBUTION_STR, " count");
  844.     tab_histdump(ks, t, n);
  845. }

One Level Up Top Level