drivers/staging/ktap/runtime/kp_str.c

   1 /*
   2  * kp_str.c - ktap string data struction 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 #include "kp_obj.h"
  28 #include "kp_str.h"
  29
  30 #ifdef __KERNEL__
  31 #include <linux/ctype.h>
  32 #include <linux/module.h>
  33 #include <linux/kallsyms.h>
  34 #include "ktap.h"
  35 #include "kp_transport.h"
  36 #include "kp_vm.h"
  37 #endif
  38
  39 #define STRING_MAXSHORTLEN      40
  40
  41 int kp_tstring_cmp(const ktap_string *ls, const ktap_string *rs)
  42 {
  43         const char *l = getstr(ls);
  44         size_t ll = ls->tsv.len;
  45         const char *r = getstr(rs);
  46         size_t lr = rs->tsv.len;
  47
  48         for (;;) {
  49                 int temp = strcmp(l, r);
  50                 if (temp != 0)
  51                         return temp;
  52                 else {
  53                         /* strings are equal up to a `\0' */
  54
  55                         /* index of first `\0' in both strings */
  56                         size_t len = strlen(l);
  57
  58                         /* r is finished? */
  59                         if (len == lr)
  60                                 return (len == ll) ? 0 : 1;
  61                         else if (len == ll)  /* l is finished? */
  62                                 return -1;
  63
  64                         /*
  65                          * both strings longer than `len';
  66                          * go on comparing (after the `\0')
  67                          */
  68                         len++;
  69                         l += len; ll -= len; r += len; lr -= len;
  70                 }
  71         }
  72 }
  73
  74 /*
  75  * equality for long strings
  76  */
  77 int kp_tstring_eqlngstr(ktap_string *a, ktap_string *b)
  78 {
  79         size_t len = a->tsv.len;
  80
  81         return (a == b) || ((len == b->tsv.len) &&
  82                 (memcmp(getstr(a), getstr(b), len) == 0));
  83 }
  84
  85 /*
  86  * equality for strings
  87  */
  88 int kp_tstring_eqstr(ktap_string *a, ktap_string *b)
  89 {
  90         return (a->tsv.tt == b->tsv.tt) &&
  91                (a->tsv.tt == KTAP_TSHRSTR ? eqshrstr(a, b) :
  92                                 kp_tstring_eqlngstr(a, b));
  93 }
  94
  95 #define STRING_HASHLIMIT        5
  96 unsigned int kp_string_hash(const char *str, size_t l, unsigned int seed)
  97 {
  98         unsigned int h = seed ^ l;
  99         size_t l1;
 100         size_t step = (l >> STRING_HASHLIMIT) + 1;
 101
 102         for (l1 = l; l1 >= step; l1 -= step)
 103                 h = h ^ ((h<<5) + (h>>2) + (u8)(str[l1 - 1]));
 104
 105         return h;
 106 }
 107
 108
 109 /*
 110  * resizes the string table
 111  */
 112 void kp_tstring_resize(ktap_state *ks, int newsize)
 113 {
 114         int i;
 115         ktap_stringtable *tb = &G(ks)->strt;
 116
 117         if (newsize > tb->size) {
 118                 kp_realloc(ks, tb->hash, tb->size, newsize, ktap_gcobject *);
 119
 120         for (i = tb->size; i < newsize; i++)
 121                 tb->hash[i] = NULL;
 122         }
 123
 124         /* rehash */
 125         for (i = 0; i < tb->size; i++) {
 126                 ktap_gcobject *p = tb->hash[i];
 127                 tb->hash[i] = NULL;
 128
 129                 while (p) {
 130                         ktap_gcobject *next = gch(p)->next;
 131                         unsigned int h = lmod(gco2ts(p)->hash, newsize);
 132
 133                         gch(p)->next = tb->hash[h];
 134                         tb->hash[h] = p;
 135                         p = next;
 136                 }
 137         }
 138
 139         if (newsize < tb->size) {
 140                 /* shrinking slice must be empty */
 141                 kp_realloc(ks, tb->hash, tb->size, newsize, ktap_gcobject *);
 142         }
 143
 144         tb->size = newsize;
 145 }
 146
 147 /*
 148  * creates a new string object
 149  */
 150 static ktap_string *createstrobj(ktap_state *ks, const char *str, size_t l,
 151                                  int tag, unsigned int h, ktap_gcobject **list)
 152 {
 153         ktap_string *ts;
 154         size_t totalsize;  /* total size of TString object */
 155
 156         totalsize = sizeof(ktap_string) + ((l + 1) * sizeof(char));
 157         ts = &kp_newobject(ks, tag, totalsize, list)->ts;
 158         ts->tsv.len = l;
 159         ts->tsv.hash = h;
 160         ts->tsv.extra = 0;
 161         memcpy(ts + 1, str, l * sizeof(char));
 162         ((char *)(ts + 1))[l] = '\0';  /* ending 0 */
 163         return ts;
 164 }
 165
 166 /*
 167  * creates a new short string, inserting it into string table
 168  */
 169 static ktap_string *newshrstr(ktap_state *ks, const char *str, size_t l,
 170                           unsigned int h)
 171 {
 172         ktap_gcobject **list;
 173         ktap_stringtable *tb = &G(ks)->strt;
 174         ktap_string *s;
 175
 176         if (tb->nuse >= (int)tb->size)
 177                 kp_tstring_resize(ks, tb->size * 2);  /* too crowded */
 178
 179         list = &tb->hash[lmod(h, tb->size)];
 180         s = createstrobj(ks, str, l, KTAP_TSHRSTR, h, list);
 181         tb->nuse++;
 182         return s;
 183 }
 184
 185 /*
 186  * checks whether short string exists and reuses it or creates a new one
 187  */
 188 static ktap_string *internshrstr(ktap_state *ks, const char *str, size_t l)
 189 {
 190         ktap_gcobject *o;
 191         ktap_global_state *g = G(ks);
 192         ktap_string *ts;
 193         unsigned int h = kp_string_hash(str, l, g->seed);
 194         unsigned long __maybe_unused flags;
 195
 196 #ifdef __KERNEL__
 197         local_irq_save(flags);
 198         arch_spin_lock(&G(ks)->str_lock);
 199 #endif
 200
 201         for (o = g->strt.hash[lmod(h, g->strt.size)]; o != NULL;
 202              o = gch(o)->next) {
 203                 ts = rawgco2ts(o);
 204
 205                 if (h == ts->tsv.hash && ts->tsv.len == l &&
 206                    (memcmp(str, getstr(ts), l * sizeof(char)) == 0))
 207                         goto out;
 208         }
 209
 210         ts = newshrstr(ks, str, l, h);  /* not found; create a new string */
 211
 212  out:
 213 #ifdef __KERNEL__
 214         arch_spin_unlock(&G(ks)->str_lock);
 215         local_irq_restore(flags);
 216 #endif
 217         return ts;
 218 }
 219
 220
 221 /*
 222  * new string (with explicit length)
 223  */
 224 ktap_string *kp_tstring_newlstr(ktap_state *ks, const char *str, size_t l)
 225 {
 226         /* short string? */
 227         if (l <= STRING_MAXSHORTLEN)
 228                 return internshrstr(ks, str, l);
 229         else
 230                 return createstrobj(ks, str, l, KTAP_TLNGSTR, G(ks)->seed,
 231                                     NULL);
 232 }
 233
 234 ktap_string *kp_tstring_newlstr_local(ktap_state *ks, const char *str, size_t l)
 235 {
 236         return createstrobj(ks, str, l, KTAP_TLNGSTR, G(ks)->seed,
 237                             &ks->gclist);
 238 }
 239
 240 /*
 241  * new zero-terminated string
 242  */
 243 ktap_string *kp_tstring_new(ktap_state *ks, const char *str)
 244 {
 245         return kp_tstring_newlstr(ks, str, strlen(str));
 246 }
 247
 248 ktap_string *kp_tstring_new_local(ktap_state *ks, const char *str)
 249 {
 250         return createstrobj(ks, str, strlen(str), KTAP_TLNGSTR, G(ks)->seed,
 251                             &ks->gclist);
 252 }
 253
 254 void kp_tstring_freeall(ktap_state *ks)
 255 {
 256         ktap_global_state *g = G(ks);
 257         int h;
 258
 259         for (h = 0; h < g->strt.size; h++) {
 260                 ktap_gcobject *o, *next;
 261                 o = g->strt.hash[h];
 262                 while (o) {
 263                         next = gch(o)->next;
 264                         kp_free(ks, o);
 265                         o = next;
 266                 }
 267                 g->strt.hash[h] = NULL;
 268         }
 269
 270         kp_free(ks, g->strt.hash);
 271 }
 272
 273 /* todo: dump long string, strt table only contain short string */
 274 void kp_tstring_dump(ktap_state *ks)
 275 {
 276         ktap_gcobject *o;
 277         ktap_global_state *g = G(ks);
 278         int h;
 279
 280         kp_printf(ks, "tstring dump: strt size: %d, nuse: %d\n", g->strt.size,
 281                                                                  g->strt.nuse);
 282         for (h = 0; h < g->strt.size; h++) {
 283                 for (o = g->strt.hash[h]; o != NULL; o = gch(o)->next) {
 284                         ktap_string *ts = rawgco2ts(o);
 285                         kp_printf(ks, "%s [%d]\n", getstr(ts), (int)ts->tsv.len);
 286                 }
 287         }
 288 }
 289
 290 #ifdef __KERNEL__
 291 /* kp_str_fmt - printf implementation */
 292
 293 /* macro to `unsign' a character */
 294 #define uchar(c)        ((unsigned char)(c))
 295
 296 #define L_ESC           '%'
 297
 298 /* valid flags in a format specification */
 299 #define FLAGS   "-+ #0"
 300
 301 #define INTFRMLEN       "ll"
 302 #define INTFRM_T        long long
 303
 304 /*
 305  * maximum size of each format specification (such as '%-099.99d')
 306  * (+10 accounts for %99.99x plus margin of error)
 307  */
 308 #define MAX_FORMAT      (sizeof(FLAGS) + sizeof(INTFRMLEN) + 10)
 309
 310 static const char *scanformat(ktap_state *ks, const char *strfrmt, char *form)
 311 {
 312         const char *p = strfrmt;
 313         while (*p != '\0' && strchr(FLAGS, *p) != NULL)
 314                 p++;  /* skip flags */
 315
 316         if ((size_t)(p - strfrmt) >= sizeof(FLAGS)/sizeof(char)) {
 317                 kp_error(ks, "invalid format (repeated flags)\n");
 318                 return NULL;
 319         }
 320
 321         if (isdigit(uchar(*p)))
 322                 p++;  /* skip width */
 323
 324         if (isdigit(uchar(*p)))
 325                 p++;  /* (2 digits at most) */
 326
 327         if (*p == '.') {
 328                 p++;
 329                 if (isdigit(uchar(*p)))
 330                         p++;  /* skip precision */
 331                 if (isdigit(uchar(*p)))
 332                         p++;  /* (2 digits at most) */
 333         }
 334
 335         if (isdigit(uchar(*p))) {
 336                 kp_error(ks, "invalid format (width or precision too long)\n");
 337                 return NULL;
 338         }
 339
 340         *(form++) = '%';
 341         memcpy(form, strfrmt, (p - strfrmt + 1) * sizeof(char));
 342         form += p - strfrmt + 1;
 343         *form = '\0';
 344         return p;
 345 }
 346
 347
 348 /*
 349  * add length modifier into formats
 350  */
 351 static void addlenmod(char *form, const char *lenmod)
 352 {
 353         size_t l = strlen(form);
 354         size_t lm = strlen(lenmod);
 355         char spec = form[l - 1];
 356
 357         strcpy(form + l - 1, lenmod);
 358         form[l + lm - 1] = spec;
 359         form[l + lm] = '\0';
 360 }
 361
 362
 363 static void ktap_argerror(ktap_state *ks, int narg, const char *extramsg)
 364 {
 365         kp_error(ks, "bad argument #%d: (%s)\n", narg, extramsg);
 366 }
 367
 368 int kp_str_fmt(ktap_state *ks, struct trace_seq *seq)
 369 {
 370         int arg = 1;
 371         size_t sfl;
 372         ktap_value *arg_fmt = kp_arg(ks, 1);
 373         int argnum = kp_arg_nr(ks);
 374         const char *strfrmt, *strfrmt_end;
 375
 376         strfrmt = svalue(arg_fmt);
 377         sfl = rawtsvalue(arg_fmt)->tsv.len;
 378         strfrmt_end = strfrmt + sfl;
 379
 380         while (strfrmt < strfrmt_end) {
 381                 if (*strfrmt != L_ESC)
 382                         trace_seq_putc(seq, *strfrmt++);
 383                 else if (*++strfrmt == L_ESC)
 384                         trace_seq_putc(seq, *strfrmt++);
 385                 else { /* format item */
 386                         char form[MAX_FORMAT];
 387
 388                         if (++arg > argnum) {
 389                                 ktap_argerror(ks, arg, "no value");
 390                                 return -1;
 391                         }
 392
 393                         strfrmt = scanformat(ks, strfrmt, form);
 394                         switch (*strfrmt++) {
 395                         case 'c':
 396                                 trace_seq_printf(seq, form,
 397                                                  nvalue(kp_arg(ks, arg)));
 398                                 break;
 399                         case 'd':  case 'i': {
 400                                 ktap_number n = nvalue(kp_arg(ks, arg));
 401                                 INTFRM_T ni = (INTFRM_T)n;
 402                                 addlenmod(form, INTFRMLEN);
 403                                 trace_seq_printf(seq, form, ni);
 404                                 break;
 405                         }
 406                         case 'p': {
 407                                 char str[KSYM_SYMBOL_LEN];
 408                                 SPRINT_SYMBOL(str, nvalue(kp_arg(ks, arg)));
 409                                 _trace_seq_puts(seq, str);
 410                                 break;
 411                         }
 412                         case 'o':  case 'u':  case 'x':  case 'X': {
 413                                 ktap_number n = nvalue(kp_arg(ks, arg));
 414                                 unsigned INTFRM_T ni = (unsigned INTFRM_T)n;
 415                                 addlenmod(form, INTFRMLEN);
 416                                 trace_seq_printf(seq, form, ni);
 417                                 break;
 418                         }
 419                         case 's': {
 420                                 ktap_value *v = kp_arg(ks, arg);
 421                                 const char *s;
 422                                 size_t l;
 423
 424                                 if (is_nil(v)) {
 425                                         _trace_seq_puts(seq, "nil");
 426                                         return 0;
 427                                 }
 428
 429                                 if (is_event(v)) {
 430                                         kp_event_tostring(ks, seq);
 431                                         return 0;
 432                                 }
 433
 434                                 s = svalue(v);
 435                                 l = rawtsvalue(v)->tsv.len;
 436                                 if (!strchr(form, '.') && l >= 100) {
 437                                         /*
 438                                          * no precision and string is too long
 439                                          * to be formatted;
 440                                          * keep original string
 441                                          */
 442                                         _trace_seq_puts(seq, s);
 443                                         break;
 444                                 } else {
 445                                         trace_seq_printf(seq, form, s);
 446                                         break;
 447                                 }
 448                         }
 449                         default: /* also treat cases `pnLlh' */
 450                                 kp_error(ks, "invalid option " KTAP_QL("%%%c")
 451                                              " to " KTAP_QL("format"),
 452                                              *(strfrmt - 1));
 453                         }
 454                 }
 455         }
 456
 457         return 0;
 458 }
 459 #endif
 460