drivers/staging/ktap/runtime/kp_tab.c

   1 /*
   2  * kp_tab.c - ktap table data structure manipulation
   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  * Copyright (C) 1994-2013 Lua.org, PUC-Rio.
   9  *  - The part of code in this file is copied from lua initially.
  10  *  - lua's MIT license is compatible with GPL.
  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  */
  25
  26 #include "../include/ktap_types.h"
  27
  28 #ifdef __KERNEL__
  29 #include <linux/spinlock.h>
  30 #include <linux/module.h>
  31 #include <linux/kallsyms.h>
  32 #include <linux/sort.h>
  33 #include "ktap.h"
  34 #include "kp_vm.h"
  35 #else
  36 static inline void sort(void *base, size_t num, size_t size,
  37                         int (*cmp_func)(const void *, const void *),
  38                         void (*swap_func)(void *, void *, int size))
  39 {}
  40 #endif
  41
  42 #include "kp_obj.h"
  43 #include "kp_str.h"
  44
  45 #ifdef __KERNEL__
  46 #define kp_tab_lock_init(t)                                             \
  47         do {                                                            \
  48                 (t)->lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED; \
  49         } while (0)
  50 #define kp_tab_lock(t)                                          \
  51         do {                                                            \
  52                 local_irq_save(flags);                                  \
  53                 arch_spin_lock(&(t)->lock);                             \
  54         } while (0)
  55 #define kp_tab_unlock(t)                                                \
  56         do {                                                            \
  57                 arch_spin_unlock(&(t)->lock);                           \
  58                 local_irq_restore(flags);                               \
  59         } while (0)
  60
  61 #else
  62 #define kp_tab_lock_init(t)
  63 #define kp_tab_lock(t)
  64 #define kp_tab_unlock(t)
  65 #endif
  66
  67 #define MAXBITS         30
  68 #define MAXASIZE        (1 << MAXBITS)
  69
  70
  71 #define NILCONSTANT     {NULL}, KTAP_TNIL
  72 const struct ktap_value ktap_nilobjectv = {NILCONSTANT};
  73 #define ktap_nilobject  (&ktap_nilobjectv)
  74
  75 static const ktap_tnode dummynode_ = {
  76         {NILCONSTANT}, /* value */
  77         {NULL, {NILCONSTANT}}, /* key */
  78 };
  79
  80 #define gnode(t,i)      (&(t)->node[i])
  81 #define gkey(n)         (&(n)->i_key.tvk)
  82 #define gval(n)         (&(n)->i_val)
  83 #define gnext(n)        ((n)->i_key.next)
  84
  85 #define twoto(x)        (1<<(x))
  86 #define sizenode(t)     (twoto((t)->lsizenode))
  87
  88 #define hashpow2(t,n)           (gnode(t, lmod((n), sizenode(t))))
  89
  90 #define hashmod(t,n)            (gnode(t, ((n) % ((sizenode(t)-1)|1))))
  91
  92 #define hashstr(t,str)          hashpow2(t, (str)->tsv.hash)
  93 #define hashboolean(t,p)        hashpow2(t, p)
  94 #define hashnum(t, n)           hashmod(t, (unsigned int)n)
  95 #define hashpointer(t,p)        hashmod(t, (unsigned long)(p))
  96
  97 #define dummynode       (&dummynode_)
  98 #define isdummy(n)      ((n) == dummynode)
  99
 100 static void table_setint(ktap_state *ks, ktap_tab *t, int key, ktap_value *v);
 101 static ktap_value *table_set(ktap_state *ks, ktap_tab *t,
 102                              const ktap_value *key);
 103 static void setnodevector(ktap_state *ks, ktap_tab *t, int size);
 104
 105 static int ceillog2(unsigned int x)
 106 {
 107         static const u8 log_2[256] = {
 108         0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 109         6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 110         7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 111         7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 112         8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 113         8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 114         8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 115         8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
 116         };
 117
 118         int l = 0;
 119
 120         x--;
 121         while (x >= 256) { l += 8; x >>= 8; }
 122         return l + log_2[x];
 123 }
 124
 125 #ifdef __KERNEL__
 126 static inline ktap_stat_data *_read_sd(const ktap_value *v,
 127                                     ktap_tnode *hnode, ktap_stat_data *hsd)
 128 {
 129         ktap_tnode *node = container_of(v, ktap_tnode, i_val);
 130         return hsd + (node - hnode);
 131 }
 132
 133 static inline ktap_stat_data *read_sd(ktap_tab *t, const ktap_value *v)
 134 {
 135         if (v >= &t->array[0] && v < &t->array[t->sizearray])
 136                 return &t->sd_arr[v - &t->array[0]];
 137         else
 138                 return _read_sd(v, t->node, t->sd_rec);
 139 }
 140
 141 #else
 142 static inline ktap_stat_data *_read_sd(const ktap_value *v,
 143                                     ktap_tnode *hnode, ktap_stat_data *hsd)
 144 {
 145         return NULL;
 146 }
 147
 148 static inline ktap_stat_data *read_sd(ktap_tab *t, const ktap_value *v)
 149 {
 150         return NULL;
 151 }
 152 #endif
 153
 154
 155 ktap_tab *kp_tab_new(ktap_state *ks)
 156 {
 157         ktap_tab *t = &kp_newobject(ks, KTAP_TTABLE, sizeof(ktap_tab),
 158                                       NULL)->h;
 159         t->flags = (u8)(~0);
 160         t->array = NULL;
 161         t->sizearray = 0;
 162         t->node = (ktap_tnode *)dummynode;
 163         t->gclist = NULL;
 164         t->with_stats = 0;
 165         t->sd_arr = NULL;
 166         t->sd_rec = NULL;
 167         setnodevector(ks, t, 0);
 168
 169         t->sorted = NULL;
 170         t->sort_head = NULL;
 171
 172         kp_tab_lock_init(t);
 173         return t;
 174 }
 175
 176 static const ktap_value *table_getint(ktap_tab *t, int key)
 177 {
 178         ktap_tnode *n;
 179
 180         if ((unsigned int)(key - 1) < (unsigned int)t->sizearray)
 181                 return &t->array[key - 1];
 182
 183         n = hashnum(t, key);
 184         do {
 185                 if (is_number(gkey(n)) && nvalue(gkey(n)) == key)
 186                         return gval(n);
 187                 else
 188                         n = gnext(n);
 189         } while (n);
 190
 191         return ktap_nilobject;
 192 }
 193
 194 const ktap_value *kp_tab_getint(ktap_tab *t, int key)
 195 {
 196         const ktap_value *val;
 197         unsigned long __maybe_unused flags;
 198
 199         kp_tab_lock(t);
 200         val = table_getint(t, key);
 201         kp_tab_unlock(t);
 202
 203         return val;
 204 }
 205
 206 static ktap_tnode *mainposition (const ktap_tab *t, const ktap_value *key)
 207 {
 208         switch (ttype(key)) {
 209         case KTAP_TNUMBER:
 210                 return hashnum(t, nvalue(key));
 211         case KTAP_TLNGSTR: {
 212                 ktap_string *s = rawtsvalue(key);
 213                 if (s->tsv.extra == 0) {  /* no hash? */
 214                         s->tsv.hash = kp_string_hash(getstr(s), s->tsv.len,
 215                                                      s->tsv.hash);
 216                         s->tsv.extra = 1;  /* now it has its hash */
 217                 }
 218                 return hashstr(t, rawtsvalue(key));
 219                 }
 220         case KTAP_TSHRSTR:
 221                 return hashstr(t, rawtsvalue(key));
 222         case KTAP_TBOOLEAN:
 223                 return hashboolean(t, bvalue(key));
 224         case KTAP_TLIGHTUSERDATA:
 225                 return hashpointer(t, pvalue(key));
 226         case KTAP_TCFUNCTION:
 227                 return hashpointer(t, fvalue(key));
 228         case KTAP_TBTRACE: {
 229                 /* use first entry as hash key, cannot use gcvalue as key */
 230                 unsigned long *entries = (unsigned long *)(btvalue(key) + 1);
 231                 return hashpointer(t, entries[0]);
 232                 }
 233         default:
 234                 return hashpointer(t, gcvalue(key));
 235         }
 236 }
 237
 238 static int arrayindex(const ktap_value *key)
 239 {
 240         if (is_number(key)) {
 241                 ktap_number n = nvalue(key);
 242                 int k = (int)n;
 243                 if ((ktap_number)k == n)
 244                         return k;
 245         }
 246
 247         /* `key' did not match some condition */
 248         return -1;
 249 }
 250
 251 /*
 252  * returns the index of a `key' for table traversals. First goes all
 253  * elements in the array part, then elements in the hash part. The
 254  * beginning of a traversal is signaled by -1.
 255  */
 256 static int findindex(ktap_state *ks, ktap_tab *t, StkId key)
 257 {
 258         int i;
 259
 260         if (is_nil(key))
 261                 return -1;  /* first iteration */
 262
 263         i = arrayindex(key);
 264         if (i > 0 && i <= t->sizearray)  /* is `key' inside array part? */
 265                 return i - 1;  /* yes; that's the index (corrected to C) */
 266         else {
 267                 ktap_tnode *n = mainposition(t, key);
 268                 for (;;) {  /* check whether `key' is somewhere in the chain */
 269                         /* key may be dead already, but it is ok to use it in `next' */
 270                         if (kp_equalobjv(ks, gkey(n), key)) {
 271                                 i = n - gnode(t, 0);  /* key index in hash table */
 272                                 /* hash elements are numbered after array ones */
 273                                 return i + t->sizearray;
 274                         } else
 275                                 n = gnext(n);
 276
 277                         if (n == NULL)
 278                                 /* key not found */
 279                                 kp_error(ks, "invalid table key to next");
 280                 }
 281         }
 282 }
 283
 284 int kp_tab_next(ktap_state *ks, ktap_tab *t, StkId key)
 285 {
 286         unsigned long __maybe_unused flags;
 287         int i;
 288
 289         kp_tab_lock(t);
 290
 291         i = findindex(ks, t, key);  /* find original element */
 292
 293         for (i++; i < t->sizearray; i++) {  /* try first array part */
 294                 if (!is_nil(&t->array[i])) {  /* a non-nil value? */
 295                         set_number(key, i+1);
 296                         set_obj(key+1, &t->array[i]);
 297                         kp_tab_unlock(t);
 298                         return 1;
 299                 }
 300         }
 301
 302         for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
 303                 if (!is_nil(gval(gnode(t, i)))) {  /* a non-nil value? */
 304                         set_obj(key, gkey(gnode(t, i)));
 305                         set_obj(key+1, gval(gnode(t, i)));
 306                         kp_tab_unlock(t);
 307                         return 1;
 308                 }
 309         }
 310
 311         kp_tab_unlock(t);
 312         return 0;  /* no more elements */
 313 }
 314
 315 #ifdef __KERNEL__
 316 int kp_tab_sort_next(ktap_state *ks, ktap_tab *t, StkId key)
 317 {
 318         unsigned long __maybe_unused flags;
 319         ktap_tnode *node = t->sort_head;
 320
 321         kp_tab_lock(t);
 322
 323         if (is_nil(key)) {
 324                 /* first iteration */
 325                 set_obj(key, gkey(node));
 326                 set_obj(key + 1, gval(node));
 327                 kp_tab_unlock(t);
 328                 return 1;
 329         }
 330
 331         while (node && !is_nil(gval(node))) {
 332                 if (kp_equalobjv(ks, gkey(node), key)) {
 333                         node = gnext(node);
 334                         if (!node)
 335                                 goto out;
 336
 337                         set_obj(key, gkey(node));
 338                         set_obj(key + 1, gval(node));
 339                         kp_tab_unlock(t);
 340                         return 1;
 341                 }
 342                 node = gnext(node);
 343         }
 344
 345  out:
 346         kp_tab_unlock(t);
 347         return 0;  /* no more elements */
 348 }
 349
 350
 351 static int default_compare(ktap_state *ks, ktap_closure *cmp_func,
 352                                 ktap_value *v1, ktap_value *v2)
 353 {
 354         return nvalue(v1) < nvalue(v2);
 355 }
 356
 357 static int closure_compare(ktap_state *ks, ktap_closure *cmp_func,
 358                                 ktap_value *v1, ktap_value *v2)
 359 {
 360         ktap_value *func;
 361         int res;
 362
 363         func = ks->top;
 364         set_closure(ks->top++, cmp_func);
 365         set_obj(ks->top++, v1);
 366         set_obj(ks->top++, v2);
 367
 368         kp_call(ks, func, 1);
 369
 370         res = !is_false(ks->top - 1);
 371
 372         ks->top = func; /* restore ks->top */
 373
 374         return res;
 375 }
 376
 377 static void insert_sorted_list(ktap_state *ks, ktap_tab *t,
 378                                 ktap_closure *cmp_func,
 379                                 ktap_value *key, ktap_value *val)
 380 {
 381         ktap_tnode *node = t->sort_head;
 382         ktap_tnode *newnode, *prevnode = NULL;
 383         int (*compare)(ktap_state *ks, ktap_closure *cmp_func,
 384                         ktap_value *v1, ktap_value *v2);
 385         int i = 0;
 386
 387         if (is_nil(gval(node))) {
 388                 *gkey(node) = *key;
 389                 *gval(node) = *val;
 390                 return;
 391         }
 392
 393         if (!cmp_func)
 394                 compare = default_compare;
 395         else
 396                 compare = closure_compare;
 397
 398         while (node) {
 399                 //if (nvalue(gval(node)) < nvalue(val)) {
 400                 if (compare(ks, cmp_func, gval(node), val)) {
 401                         prevnode = node;
 402                         node = gnext(node);
 403                         continue;
 404                 } else
 405                         break;
 406         }
 407
 408         /* find free position */
 409         while (!is_nil(gval(&t->sorted[i]))) {
 410                 i++;
 411         }
 412
 413         newnode = &t->sorted[i];
 414         *gkey(newnode) = *key;
 415         *gval(newnode) = *val;
 416         gnext(newnode) = node;
 417         if (prevnode)
 418                 gnext(prevnode) = newnode;
 419         else
 420                 t->sort_head = newnode;
 421 }
 422
 423 void kp_tab_sort(ktap_state *ks, ktap_tab *t, ktap_closure *cmp_func)
 424 {
 425         unsigned long __maybe_unused flags;
 426         int size = t->sizearray + sizenode(t);
 427         int i;
 428
 429         kp_tab_lock(t);
 430
 431         kp_realloc(ks, t->sorted, 0, size, ktap_tnode);
 432         memset(t->sorted, 0, size * sizeof(ktap_tnode));
 433         t->sort_head = t->sorted;
 434
 435         for (i = 0; i < t->sizearray; i++) {
 436                 ktap_value *v = &t->array[i];
 437                 ktap_value key;
 438
 439                 if (!is_nil(v)) {
 440                         set_number(&key, i + 1);
 441                         insert_sorted_list(ks, t, cmp_func, &key, v);
 442                 }
 443         }
 444
 445         for (i = 0; i < sizenode(t); i++) {
 446                 ktap_tnode *node = &t->node[i];
 447
 448                 if (is_nil(gkey(node)))
 449                         continue;
 450
 451                 insert_sorted_list(ks, t, cmp_func, gkey(node), gval(node));
 452         }
 453
 454         kp_tab_unlock(t);
 455 }
 456 #endif
 457
 458 static int computesizes (int nums[], int *narray)
 459 {
 460         int i;
 461         int twotoi;  /* 2^i */
 462         int a = 0;  /* number of elements smaller than 2^i */
 463         int na = 0;  /* number of elements to go to array part */
 464         int n = 0;  /* optimal size for array part */
 465
 466         for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
 467                 if (nums[i] > 0) {
 468                         a += nums[i];
 469                         /* more than half elements present? */
 470                         if (a > twotoi/2) {
 471                                 /* optimal size (till now) */
 472                                 n = twotoi;
 473                                 /*
 474                                  * all elements smaller than n will go to
 475                                  * array part
 476                                  */
 477                                 na = a;
 478                         }
 479                 }
 480                 if (a == *narray)
 481                         break;  /* all elements already counted */
 482         }
 483         *narray = n;
 484         return na;
 485 }
 486
 487
 488 static int countint(const ktap_value *key, int *nums)
 489 {
 490         int k = arrayindex(key);
 491
 492         /* is `key' an appropriate array index? */
 493         if (0 < k && k <= MAXASIZE) {
 494                 nums[ceillog2(k)]++;  /* count as such */
 495                 return 1;
 496         } else
 497                 return 0;
 498 }
 499
 500
 501 static int numusearray(const ktap_tab *t, int *nums)
 502 {
 503         int lg;
 504         int ttlg;  /* 2^lg */
 505         int ause = 0;  /* summation of `nums' */
 506         int i = 1;  /* count to traverse all array keys */
 507
 508         /* for each slice */
 509         for (lg=0, ttlg=1; lg <= MAXBITS; lg++, ttlg *= 2) {
 510                 int lc = 0;  /* counter */
 511                 int lim = ttlg;
 512
 513                 if (lim > t->sizearray) {
 514                         lim = t->sizearray;  /* adjust upper limit */
 515                         if (i > lim)
 516                                 break;  /* no more elements to count */
 517                 }
 518
 519                 /* count elements in range (2^(lg-1), 2^lg] */
 520                 for (; i <= lim; i++) {
 521                         if (!is_nil(&t->array[i-1]))
 522                                 lc++;
 523                 }
 524                 nums[lg] += lc;
 525                 ause += lc;
 526         }
 527         return ause;
 528 }
 529
 530 static int numusehash(const ktap_tab *t, int *nums, int *pnasize)
 531 {
 532         int totaluse = 0;  /* total number of elements */
 533         int ause = 0;  /* summation of `nums' */
 534         int i = sizenode(t);
 535
 536         while (i--) {
 537                 ktap_tnode *n = &t->node[i];
 538                 if (!is_nil(gval(n))) {
 539                         ause += countint(gkey(n), nums);
 540                         totaluse++;
 541                 }
 542         }
 543
 544         *pnasize += ause;
 545         return totaluse;
 546 }
 547
 548 static void update_array_sd(ktap_tab *t)
 549 {
 550         int i;
 551
 552         for (i = 0; i < t->sizearray; i++) {
 553                 ktap_value *v = &t->array[i];
 554
 555                 if (!is_statdata(v))
 556                         continue;
 557
 558                 set_statdata(v, &t->sd_arr[i]);
 559         }
 560 }
 561
 562 static void setarrayvector(ktap_state *ks, ktap_tab *t, int size)
 563 {
 564         int i;
 565
 566         kp_realloc(ks, t->array, t->sizearray, size, ktap_value);
 567         if (t->with_stats) {
 568                 kp_realloc(ks, t->sd_arr, t->sizearray, size,
 569                                 ktap_stat_data);
 570                 update_array_sd(t);
 571         }
 572
 573         for (i = t->sizearray; i < size; i++)
 574                 set_nil(&t->array[i]);
 575
 576         t->sizearray = size;
 577 }
 578
 579 static void setnodevector(ktap_state *ks, ktap_tab *t, int size)
 580 {
 581         int lsize;
 582
 583         if (size == 0) {  /* no elements to hash part? */
 584                 t->node = (ktap_tnode *)dummynode;  /* use common `dummynode' */
 585                 lsize = 0;
 586         } else {
 587                 int i;
 588                 lsize = ceillog2(size);
 589                 if (lsize > MAXBITS) {
 590                         kp_error(ks, "table overflow\n");
 591                         return;
 592                 }
 593
 594                 size = twoto(lsize);
 595                 t->node = kp_malloc(ks, size * sizeof(ktap_tnode));
 596                 if (t->with_stats)
 597                         t->sd_rec = kp_malloc(ks, size *
 598                                                 sizeof(ktap_stat_data));
 599                 for (i = 0; i < size; i++) {
 600                         ktap_tnode *n = gnode(t, i);
 601                         gnext(n) = NULL;
 602                         set_nil(gkey(n));
 603                         set_nil(gval(n));
 604                 }
 605         }
 606
 607         t->lsizenode = (u8)lsize;
 608         t->lastfree = gnode(t, size);  /* all positions are free */
 609 }
 610
 611 static void table_resize(ktap_state *ks, ktap_tab *t, int nasize, int nhsize)
 612 {
 613         int oldasize = t->sizearray;
 614         int oldhsize = t->lsizenode;
 615         ktap_tnode *nold = t->node;  /* save old hash */
 616         ktap_stat_data *sd_rec_old = t->sd_rec;  /* save stat_data */
 617         int i;
 618
 619 #ifdef __KERNEL__
 620         kp_verbose_printf(ks, "table resize, nasize: %d, nhsize: %d\n",
 621                                 nasize, nhsize);
 622 #endif
 623
 624         if (nasize > oldasize)  /* array part must grow? */
 625                 setarrayvector(ks, t, nasize);
 626
 627         /* create new hash part with appropriate size */
 628         setnodevector(ks, t, nhsize);
 629
 630         if (nasize < oldasize) {  /* array part must shrink? */
 631                 t->sizearray = nasize;
 632                 /* re-insert elements from vanishing slice */
 633                 for (i = nasize; i < oldasize; i++) {
 634                         if (!is_nil(&t->array[i])) {
 635                                 ktap_value *v;
 636                                 v = (ktap_value *)table_getint(t, i + 1);
 637                                 set_obj(v, &t->array[i]);
 638
 639                                 if (t->with_stats) {
 640                                         *read_sd(t, v) = t->sd_arr[i];
 641                                         set_statdata(v, read_sd(t, v));
 642                                 }
 643                         }
 644                 }
 645
 646                 /* shrink array */
 647                 kp_realloc(ks, t->array, oldasize, nasize, ktap_value);
 648                 if (t->with_stats) {
 649                         kp_realloc(ks, t->sd_arr, oldasize, nasize,
 650                                         ktap_stat_data);
 651                         update_array_sd(t);
 652                 }
 653         }
 654
 655         /* re-insert elements from hash part */
 656         for (i = twoto(oldhsize) - 1; i >= 0; i--) {
 657                 ktap_tnode *old = nold + i;
 658                 if (!is_nil(gval(old))) {
 659                         ktap_value *v = table_set(ks, t, gkey(old));
 660                         /*
 661                          * doesn't need barrier/invalidate cache, as entry was
 662                          * already present in the table
 663                          */
 664                         set_obj(v, gval(old));
 665
 666                         if (t->with_stats) {
 667                                 ktap_stat_data *sd;
 668
 669                                 sd = read_sd(t, v);
 670                                 *sd = *_read_sd(gval(old), nold, sd_rec_old);
 671                                 set_statdata(v, sd);
 672                         }
 673                 }
 674         }
 675
 676         if (!isdummy(nold)) {
 677                 kp_free(ks, nold); /* free old array */
 678                 kp_free(ks, sd_rec_old);
 679         }
 680 }
 681
 682 void kp_tab_resize(ktap_state *ks, ktap_tab *t, int nasize, int nhsize)
 683 {
 684         unsigned long __maybe_unused flags;
 685
 686         kp_tab_lock(t);
 687         table_resize(ks, t, nasize, nhsize);
 688         kp_tab_unlock(t);
 689 }
 690
 691 void kp_tab_resizearray(ktap_state *ks, ktap_tab *t, int nasize)
 692 {
 693         unsigned long __maybe_unused flags;
 694         int nsize;
 695
 696         kp_tab_lock(t);
 697
 698         nsize = isdummy(t->node) ? 0 : sizenode(t);
 699         table_resize(ks, t, nasize, nsize);
 700
 701         kp_tab_unlock(t);
 702 }
 703
 704 static void rehash(ktap_state *ks, ktap_tab *t, const ktap_value *ek)
 705 {
 706         int nasize, na;
 707         /* nums[i] = number of keys with 2^(i-1) < k <= 2^i */
 708         int nums[MAXBITS+1];
 709         int i;
 710         int totaluse;
 711
 712         for (i = 0; i <= MAXBITS; i++)
 713                 nums[i] = 0;  /* reset counts */
 714
 715         nasize = numusearray(t, nums);  /* count keys in array part */
 716         totaluse = nasize;  /* all those keys are integer keys */
 717         totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
 718         /* count extra key */
 719         nasize += countint(ek, nums);
 720         totaluse++;
 721         /* compute new size for array part */
 722         na = computesizes(nums, &nasize);
 723         /* resize the table to new computed sizes */
 724         table_resize(ks, t, nasize, totaluse - na);
 725 }
 726
 727
 728 static ktap_tnode *getfreepos(ktap_tab *t)
 729 {
 730         while (t->lastfree > t->node) {
 731                 t->lastfree--;
 732                 if (is_nil(gkey(t->lastfree)))
 733                         return t->lastfree;
 734         }
 735         return NULL;  /* could not find a free place */
 736 }
 737
 738
 739 static ktap_value *table_newkey(ktap_state *ks, ktap_tab *t,
 740                                 const ktap_value *key)
 741 {
 742         ktap_tnode *mp;
 743         ktap_value newkey;
 744
 745         mp = mainposition(t, key);
 746         if (!is_nil(gval(mp)) || isdummy(mp)) {  /* main position is taken? */
 747                 ktap_tnode *othern;
 748                 ktap_tnode *n = getfreepos(t);  /* get a free place */
 749                 if (n == NULL) {  /* cannot find a free place? */
 750                         rehash(ks, t, key);  /* grow table */
 751                         /* insert key into grown table */
 752                         return table_set(ks, t, key);
 753                 }
 754
 755                 othern = mainposition(t, gkey(mp));
 756                 if (othern != mp) {
 757                         /* is colliding node out of its main position? */
 758
 759                         /* move colliding node into free position */
 760                         while (gnext(othern) != mp)
 761                                 othern = gnext(othern);  /* find previous */
 762
 763                         /* redo the chain with `n' in place of `mp' */
 764                         gnext(othern) = n;
 765
 766                         /* copy colliding node into free pos */
 767                         *n = *mp;
 768
 769                         if (t->with_stats) {
 770                                 ktap_stat_data *sd = read_sd(t, gval(n));
 771                                 *sd = *read_sd(t, gval(mp));
 772                                 set_statdata(gval(n), sd);
 773                         }
 774
 775                         gnext(mp) = NULL;  /* now `mp' is free */
 776                         set_nil(gval(mp));
 777                 } else {
 778                         /* colliding node is in its own main position */
 779
 780                         /* new node will go into free position */
 781                         gnext(n) = gnext(mp);  /* chain new position */
 782                         gnext(mp) = n;
 783                         mp = n;
 784                 }
 785         }
 786
 787         /* special handling for cloneable object, maily for btrace object */
 788         if (is_needclone(key))
 789                 kp_objclone(ks, key, &newkey, &t->gclist);
 790         else
 791                 newkey = *key;
 792
 793         set_obj(gkey(mp), &newkey);
 794         return gval(mp);
 795 }
 796
 797
 798 /*
 799  * search function for short strings
 800  */
 801 static const ktap_value *table_getstr(ktap_tab *t, ktap_string *key)
 802 {
 803         ktap_tnode *n = hashstr(t, key);
 804
 805         do {  /* check whether `key' is somewhere in the chain */
 806                 if (is_shrstring(gkey(n)) && eqshrstr(rawtsvalue(gkey(n)),
 807                                                                 key))
 808                         return gval(n);  /* that's it */
 809                 else
 810                         n = gnext(n);
 811         } while (n);
 812
 813         return ktap_nilobject;
 814 }
 815
 816
 817 /*
 818  * main search function
 819  */
 820 static const ktap_value *table_get(ktap_tab *t, const ktap_value *key)
 821 {
 822         switch (ttype(key)) {
 823         case KTAP_TNIL:
 824                 return ktap_nilobject;
 825         case KTAP_TSHRSTR:
 826                 return table_getstr(t, rawtsvalue(key));
 827         case KTAP_TNUMBER: {
 828                 ktap_number n = nvalue(key);
 829                 int k = (int)n;
 830                 if ((ktap_number)k == nvalue(key)) /* index is int? */
 831                         return table_getint(t, k);  /* use specialized version */
 832                 /* else go through */
 833         }
 834         default: {
 835                 ktap_tnode *n = mainposition(t, key);
 836                 do {  /* check whether `key' is somewhere in the chain */
 837                         if (rawequalobj(gkey(n), key))
 838                                 return gval(n);  /* that's it */
 839                         else
 840                                 n = gnext(n);
 841                 } while (n);
 842
 843                 return ktap_nilobject;
 844         }
 845         }
 846 }
 847
 848 const ktap_value *kp_tab_get(ktap_tab *t, const ktap_value *key)
 849 {
 850         const ktap_value *val;
 851         unsigned long __maybe_unused flags;
 852
 853         kp_tab_lock(t);
 854         val = table_get(t, key);
 855         kp_tab_unlock(t);
 856
 857         return val;
 858 }
 859
 860 static ktap_value *table_set(ktap_state *ks, ktap_tab *t,
 861                              const ktap_value *key)
 862 {
 863         const ktap_value *p = table_get(t, key);
 864
 865         if (p != ktap_nilobject)
 866                 return (ktap_value *)p;
 867         else
 868                 return table_newkey(ks, t, key);
 869 }
 870
 871 void kp_tab_setvalue(ktap_state *ks, ktap_tab *t,
 872                        const ktap_value *key, ktap_value *val)
 873 {
 874         unsigned long __maybe_unused flags;
 875
 876         if (is_nil(key)) {
 877                 kp_printf(ks, "table index is nil\n");
 878                 kp_exit(ks);
 879                 return;
 880         }
 881
 882         kp_tab_lock(t);
 883         set_obj(table_set(ks, t, key), val);
 884         kp_tab_unlock(t);
 885 }
 886
 887 static void table_setint(ktap_state *ks, ktap_tab *t, int key, ktap_value *v)
 888 {
 889         const ktap_value *p;
 890         ktap_value *cell;
 891
 892         p = table_getint(t, key);
 893
 894         if (p != ktap_nilobject)
 895                 cell = (ktap_value *)p;
 896         else {
 897                 ktap_value k;
 898                 set_number(&k, key);
 899                 cell = table_newkey(ks, t, &k);
 900         }
 901
 902         set_obj(cell, v);
 903 }
 904
 905 void kp_tab_setint(ktap_state *ks, ktap_tab *t, int key, ktap_value *val)
 906 {
 907         unsigned long __maybe_unused flags;
 908
 909         kp_tab_lock(t);
 910         table_setint(ks, t, key, val);
 911         kp_tab_unlock(t);
 912 }
 913
 914 void kp_tab_atomic_inc(ktap_state *ks, ktap_tab *t, ktap_value *key, int n)
 915 {
 916         unsigned long __maybe_unused flags;
 917         ktap_value *v;
 918
 919         if (is_nil(key)) {
 920                 kp_printf(ks, "table index is nil\n");
 921                 kp_exit(ks);
 922                 return;
 923         }
 924
 925         kp_tab_lock(t);
 926
 927         v = table_set(ks, t, key);
 928         if (is_nil(v)) {
 929                 set_number(v, n);
 930         } else
 931                 set_number(v, nvalue(v) + n);
 932
 933         kp_tab_unlock(t);
 934 }
 935
 936 int kp_tab_length(ktap_state *ks, ktap_tab *t)
 937 {
 938         unsigned long __maybe_unused flags;
 939         int i, len = 0;
 940
 941         kp_tab_lock(t);
 942
 943         for (i = 0; i < t->sizearray; i++) {
 944                 ktap_value *v = &t->array[i];
 945
 946                 if (is_nil(v))
 947                         continue;
 948                 len++;
 949         }
 950
 951         for (i = 0; i < sizenode(t); i++) {
 952                 ktap_tnode *n = &t->node[i];
 953
 954                 if (is_nil(gkey(n)))
 955                         continue;
 956
 957                 len++;
 958         }
 959
 960         kp_tab_unlock(t);
 961         return len;
 962 }
 963
 964 void kp_tab_free(ktap_state *ks, ktap_tab *t)
 965 {
 966         if (t->sizearray > 0) {
 967                 kp_free(ks, t->array);
 968                 kp_free(ks, t->sd_arr);
 969         }
 970
 971         if (!isdummy(t->node)) {
 972                 kp_free(ks, t->node);
 973                 kp_free(ks, t->sd_rec);
 974         }
 975
 976         kp_free(ks, t->sorted);
 977         kp_free_gclist(ks, t->gclist);
 978         kp_free(ks, t);
 979 }
 980
 981 void kp_tab_dump(ktap_state *ks, ktap_tab *t)
 982 {
 983         int i;
 984
 985         for (i = 0; i < t->sizearray; i++) {
 986                 ktap_value *v = &t->array[i];
 987
 988                 if (is_nil(v))
 989                         continue;
 990
 991                 kp_printf(ks, "%d:\t", i + 1);
 992                 kp_showobj(ks, v);
 993                 kp_puts(ks, "\n");
 994         }
 995
 996         for (i = 0; i < sizenode(t); i++) {
 997                 ktap_tnode *n = &t->node[i];
 998
 999                 if (is_nil(gkey(n)))
1000                         continue;
1001
1002                 kp_showobj(ks, gkey(n));
1003                 kp_puts(ks, ":\t");
1004                 kp_showobj(ks, gval(n));
1005                 kp_puts(ks, "\n");
1006         }
1007 }
1008
1009 /*
1010  * table-clear only set nil of all elements, not free t->array and nodes.
1011  * we assume user will reuse table soon after clear table, so reserve array
1012  * and nodes will avoid memory allocation when insert key-value again.
1013  */
1014 void kp_tab_clear(ktap_state *ks, ktap_tab *t)
1015 {
1016         unsigned long __maybe_unused flags;
1017
1018         kp_tab_lock(t);
1019
1020         memset(t->array, 0, t->sizearray * sizeof(ktap_value));
1021         memset(t->node, 0, sizenode(t) * sizeof(ktap_tnode));
1022
1023         kp_tab_unlock(t);
1024 }
1025
1026 #ifdef __KERNEL__
1027 static void string_convert(char *output, const char *input)
1028 {
1029         if (strlen(input) > 32) {
1030                 strncpy(output, input, 32-4);
1031                 memset(output + 32-4, '.', 3);
1032         } else
1033                 memcpy(output, input, strlen(input));
1034 }
1035
1036 struct table_hist_record {
1037         ktap_value key;
1038         ktap_value val;
1039 };
1040
1041 static int hist_record_cmp(const void *r1, const void *r2)
1042 {
1043         const struct table_hist_record *i = r1;
1044         const struct table_hist_record *j = r2;
1045
1046         if ((nvalue(&i->val) == nvalue(&j->val))) {
1047                 return 0;
1048         } else if ((nvalue(&i->val) < nvalue(&j->val))) {
1049                 return 1;
1050         } else
1051                 return -1;
1052 }
1053
1054 /* todo: make histdump to be faster */
1055
1056 /* histogram: key should be number or string, value must be number */
1057 static void table_histdump(ktap_state *ks, ktap_tab *t, int shownums)
1058 {
1059         struct table_hist_record *thr;
1060         unsigned long __maybe_unused flags;
1061         char dist_str[40];
1062         int i, ratio, total = 0, count = 0, top_num, is_kernel_address = 0;
1063         int size, num;
1064
1065         size = sizeof(*thr) * (t->sizearray + sizenode(t));
1066         thr = kp_malloc(ks, size);
1067         if (!thr) {
1068                 kp_error(ks, "Cannot allocate %d of histogram memory", size);
1069                 return;
1070         }
1071
1072         kp_tab_lock(t);
1073
1074         for (i = 0; i < t->sizearray; i++) {
1075                 ktap_value *v = &t->array[i];
1076
1077                 if (is_nil(v))
1078                         continue;
1079
1080                 if (is_number(v))
1081                         num = nvalue(v);
1082                 else if (is_statdata(v))
1083                         num = sdvalue(v)->count;
1084                 else {
1085                         kp_tab_unlock(t);
1086                         goto error;
1087                 }
1088
1089                 set_number(&thr[count].key, i + 1);
1090                 set_number(&thr[count].val, num);
1091                 count++;
1092                 total += num;
1093         }
1094
1095         for (i = 0; i < sizenode(t); i++) {
1096                 ktap_tnode *n = &t->node[i];
1097                 ktap_value *v = gval(n);
1098
1099                 if (is_nil(gkey(n)))
1100                         continue;
1101
1102                 if (is_number(v))
1103                         num = nvalue(v);
1104                 else if (is_statdata(v))
1105                         num = sdvalue(v)->count;
1106                 else {
1107                         kp_tab_unlock(t);
1108                         goto error;
1109                 }
1110
1111                 set_obj(&thr[count].key, gkey(n));
1112                 set_number(&thr[count].val, num);
1113                 count++;
1114                 total += num;
1115         }
1116
1117         kp_tab_unlock(t);
1118
1119         sort(thr, count, sizeof(struct table_hist_record),
1120              hist_record_cmp, NULL);
1121
1122         dist_str[sizeof(dist_str) - 1] = '\0';
1123
1124         /* check the first key is a kernel text symbol or not */
1125         if (is_number(&thr[0].key)) {
1126                 char str[KSYM_SYMBOL_LEN];
1127
1128                 SPRINT_SYMBOL(str, nvalue(&thr[0].key));
1129                 if (str[0] != '0' || str[1] != 'x')
1130                         is_kernel_address = 1;
1131         }
1132
1133         top_num = min(shownums, count);
1134         for (i = 0; i < top_num; i++) {
1135                 ktap_value *key = &thr[i].key;
1136                 ktap_value *val = &thr[i].val;
1137
1138                 memset(dist_str, ' ', sizeof(dist_str) - 1);
1139                 ratio = (nvalue(val) * (sizeof(dist_str) - 1)) / total;
1140                 memset(dist_str, '@', ratio);
1141
1142                 if (is_string(key)) {
1143                         char buf[32 + 1] = {0};
1144
1145                         string_convert(buf, svalue(key));
1146                         kp_printf(ks, "%32s |%s%-7d\n", buf, dist_str,
1147                                       nvalue(val));
1148                 } else if (is_number(key)) {
1149                         char str[KSYM_SYMBOL_LEN];
1150                         char buf[32 + 1] = {0};
1151
1152                         if (is_kernel_address) {
1153                                 /* suppose it's a symbol, fix it in future */
1154                                 SPRINT_SYMBOL(str, nvalue(key));
1155                                 string_convert(buf, str);
1156                                 kp_printf(ks, "%32s |%s%-7d\n", buf, dist_str,
1157                                                 nvalue(val));
1158                         } else {
1159                                 kp_printf(ks, "%32d |%s%-7d\n", nvalue(key),
1160                                                 dist_str, nvalue(val));
1161                         }
1162                 }
1163         }
1164
1165         if (count > shownums)
1166                 kp_printf(ks, "%32s |\n", "...");
1167
1168         goto out;
1169
1170  error:
1171         kp_puts(ks, "error: table histogram only handle "
1172                         " (key: string/number val: number)\n");
1173  out:
1174         kp_free(ks, thr);
1175 }
1176
1177 #define HISTOGRAM_DEFAULT_TOP_NUM       20
1178
1179 #define DISTRIBUTION_STR "------------- Distribution -------------"
1180 void kp_tab_histogram(ktap_state *ks, ktap_tab *t)
1181 {
1182         kp_printf(ks, "%32s%s%s\n", "value ", DISTRIBUTION_STR, " count");
1183         table_histdump(ks, t, HISTOGRAM_DEFAULT_TOP_NUM);
1184 }
1185
1186 /*
1187  * Parallel Table
1188  */
1189
1190 void kp_statdata_dump(ktap_state *ks, ktap_stat_data *sd)
1191 {
1192         kp_printf(ks, "[count: %6d sum: %6d max: %6d min: %6d avg: %6d]",
1193                 sd->count, sd->sum, sd->max, sd->min, sd->sum/sd->count);
1194 }
1195
1196 static void statdata_add(ktap_stat_data *sd1, ktap_stat_data *sd2)
1197 {
1198         sd2->count += sd1->count;
1199         sd2->sum += sd1->sum;
1200         if (sd1->max > sd2->max)
1201                 sd2->max = sd1->max;
1202         if (sd1->min < sd2->min)
1203                 sd2->min = sd1->min;
1204 }
1205
1206 static void merge_table(ktap_state *ks, ktap_tab *t1, ktap_tab *t2)
1207 {
1208         unsigned long __maybe_unused flags;
1209         ktap_value *newv;
1210         ktap_value n;
1211         int i;
1212
1213         kp_tab_lock(t1);
1214         kp_tab_lock(t2);
1215
1216         for (i = 0; i < t1->sizearray; i++) {
1217                 ktap_value *v = &t1->array[i];
1218                 ktap_stat_data *sd;
1219
1220                 if (is_nil(v))
1221                         continue;
1222
1223                 set_number(&n, i);
1224
1225                 newv = table_set(ks, t2, &n);
1226                 sd = read_sd(t2, newv);
1227                 if (is_nil(newv)) {
1228                         *sd = *read_sd(t1, v);
1229                         set_statdata(newv, sd);
1230                 } else
1231                         statdata_add(read_sd(t1, v), sd);
1232         }
1233
1234         for (i = 0; i < sizenode(t1); i++) {
1235                 ktap_tnode *node = &t1->node[i];
1236
1237                 if (is_nil(gkey(node)))
1238                         continue;
1239
1240                 newv = table_set(ks, t2, gkey(node));
1241                 if (is_nil(newv)) {
1242                         *read_sd(t2, newv) = *read_sd(t1, gval(node));
1243                         set_statdata(newv, read_sd(t2, newv));
1244                 } else
1245                         statdata_add(read_sd(t1, gval(node)),
1246                                      read_sd(t2, newv));
1247         }
1248
1249         kp_tab_unlock(t2);
1250         kp_tab_unlock(t1);
1251 }
1252
1253 ktap_tab *kp_ptab_synthesis(ktap_state *ks, ktap_ptab *ph)
1254 {
1255         ktap_tab *agg;
1256         int cpu;
1257
1258         agg = ph->agg;
1259
1260         /* clear the table content before store new elements */
1261         kp_tab_clear(ks, agg);
1262
1263         for_each_possible_cpu(cpu) {
1264                 ktap_tab **t = per_cpu_ptr(ph->tbl, cpu);
1265                 merge_table(ks, *t, agg);
1266         }
1267
1268         return agg;
1269 }
1270
1271 void kp_ptab_dump(ktap_state *ks, ktap_ptab *ph)
1272 {
1273         kp_tab_dump(ks, kp_ptab_synthesis(ks, ph));
1274 }
1275
1276 ktap_ptab *kp_ptab_new(ktap_state *ks)
1277 {
1278         ktap_ptab *ph;
1279         int cpu;
1280
1281         ph = &kp_newobject(ks, KTAP_TPTABLE, sizeof(ktap_ptab),
1282                         NULL)->ph;
1283         ph->tbl = alloc_percpu(ktap_tab *);
1284
1285         for_each_possible_cpu(cpu) {
1286                 ktap_tab **t = per_cpu_ptr(ph->tbl, cpu);
1287                 *t = kp_tab_new(ks);
1288
1289                 (*t)->with_stats = 1;
1290
1291                 /* todo: make this value to be configuable, MAXENTRIES? */
1292                 table_resize(ks, *t, 0, 2000);
1293         }
1294
1295         ph->agg = kp_tab_new(ks);
1296         ph->agg->with_stats = 1;
1297         table_resize(ks, ph->agg, 0, 2000);
1298
1299         return ph;
1300 }
1301
1302 void kp_ptab_free(ktap_state *ks, ktap_ptab *ph)
1303 {
1304         free_percpu(ph->tbl);
1305         kp_free(ks, ph);
1306 }
1307
1308 void kp_ptab_set(ktap_state *ks, ktap_ptab *ph,
1309                                  ktap_value *key, ktap_value *val)
1310 {
1311         ktap_tab *t = *__this_cpu_ptr(ph->tbl);
1312         unsigned long __maybe_unused flags;
1313         ktap_value *v;
1314         ktap_stat_data *sd;
1315         int aggval;;
1316
1317         if (unlikely(!is_number(val))) {
1318                 kp_error(ks, "add non number value to aggregation table\n");
1319                 return;
1320         }
1321
1322         aggval = nvalue(val);
1323
1324         kp_tab_lock(t);
1325
1326         v = table_set(ks, t, key);
1327         sd = read_sd(t, v);
1328
1329         if (is_nil(v)) {
1330                 sd->count = 1;
1331                 sd->sum = sd->min = sd->max = aggval;
1332                 set_statdata(v, sd);
1333                 kp_tab_unlock(t);
1334                 return;
1335         }
1336
1337         sd->count++;
1338         sd->sum += aggval;
1339         if (aggval > sd->max)
1340                 sd->max = aggval;
1341         if (aggval < sd->min)
1342                 sd->min = aggval;
1343
1344         kp_tab_unlock(t);
1345 }
1346
1347 void kp_ptab_get(ktap_state *ks, ktap_ptab *ph,
1348                                  ktap_value *key, ktap_value *val)
1349 {
1350         unsigned long __maybe_unused flags;
1351         ktap_stat_data sd, *aggsd;
1352         const ktap_value *v;
1353         ktap_value *aggval;
1354         int cpu;
1355
1356         sd.count = sd.sum = sd.max = sd.min = -1;
1357
1358         for_each_possible_cpu(cpu) {
1359                 ktap_tab **t = per_cpu_ptr(ph->tbl, cpu);
1360
1361                 kp_tab_lock(*t);
1362                 v = table_get(*t, key);
1363                 if (is_nil(v)) {
1364                         kp_tab_unlock(*t);
1365                         continue;
1366                 }
1367
1368                 if (sd.count == -1) {
1369                         sd = *read_sd(*t, v);
1370                         kp_tab_unlock(*t);
1371                         continue;
1372                 }
1373
1374                 statdata_add(read_sd(*t, v), &sd);
1375                 kp_tab_unlock(*t);
1376         }
1377
1378         if (sd.count == -1) {
1379                 set_nil(val);
1380                 return;
1381         }
1382
1383         kp_tab_lock(ph->agg);
1384         aggval = table_set(ks, ph->agg, key);
1385         aggsd = read_sd(ph->agg, aggval);
1386         *aggsd = sd;
1387         set_statdata(aggval, aggsd);
1388         set_statdata(val, aggsd);
1389         kp_tab_unlock(ph->agg);
1390 }
1391
1392 void kp_ptab_histogram(ktap_state *ks, ktap_ptab *ph)
1393 {
1394         kp_tab_histogram(ks, kp_ptab_synthesis(ks, ph));
1395 }
1396 #endif