One Level Up Top Level

runtime/kp_str.c - ktap

Functions defined

Macros defined

Source code

  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. * 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 "../include/ktap_types.h"
  27. #include "kp_obj.h"
  28. #include "kp_str.h"
  29. #include "kp_mempool.h"

  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. #include "kp_events.h"

  39. ‌int kp_str_cmp(const ktap_str_t *ls, const ktap_str_t *rs)
  40. {
  41.     const char *l = getstr(ls);
  42.     size_t ll = ls->len;
  43.     const char *r = getstr(rs);
  44.     size_t lr = rs->len;

  46.     for (;;) {
  47.         int temp = strcmp(l, r);
  48.         if (temp != 0)
  49.             return temp;
  50.         else {
  51.             /* strings are equal up to a `\0' */

  53.             /* index of first `\0' in both strings */
  54.             size_t len = strlen(l);

  56.             /* r is finished? */
  57.             if (len == lr)
  58.                 return (len == ll) ? 0 : 1;
  59.             else if (len == ll)  /* l is finished? */
  60.                 return -1;

  62.             /*
  63.              * both strings longer than `len';
  64.              * go on comparing (after the `\0')
  65.              */
  66.             len++;
  67.             l += len; ll -= len; r += len; lr -= len;
  68.         }
  69.     }
  70. }

  72. /* Fast string data comparison. Caveat: unaligned access to 1st string! */
  73. ‌static __always_inline int str_fastcmp(const char *a, const char *b, int len)
  74. {
  75.     int i = 0;

  77.     kp_assert(len > 0);
  78.     kp_assert((((uintptr_t)a + len - 1)&(PAGE_SIZE - 1)) <= PAGE_SIZE - 4);

  80.     do {  /* Note: innocuous access up to end of string + 3. */
  81.         uint32_t v = *(uint32_t *)(a + i) ^ *(const uint32_t *)(b + i);
  82.         if (v) {
  83.             i -= len;
  84. #if KP_LE
  85.             return (int32_t)i >= -3 ? (v << (32 + (i << 3))) : 1;
  86. #else
  87.             return (int32_t)i >= -3 ? (v >> (32 + (i << 3))) : 1;
  88. #endif
  89.         }
  90.         i += 4;
  91.     } while (i < len);
  92.     return 0;
  93. }


  96. //TODO: change hash algo

  98. ‌#define STRING_HASHLIMIT    5
  99. ‌static __always_inline unsigned int kp_str_hash(const char *str, size_t len)
  100. {
  101.     unsigned int h = 201236 ^ len;
  102.     size_t step = (len >> STRING_HASHLIMIT) + 1;
  103.     size_t l1;

  105.     for (l1 = len; l1 >= step; l1 -= step)
  106.         h = h ^ ((h<<5) + (h>>2) + (u8)(str[l1 - 1]));

  108.     return h;
  109. }


  112. /*
  113. * resizes the string table
  114. */
  115. ‌int kp_str_resize(ktap_state_t *ks, int newmask)
  116. {
  117.     ktap_global_state_t *g = G(ks);
  118.     ktap_str_t **newhash;

  120.     newhash = kp_zalloc(ks, (newmask + 1) * sizeof(ktap_str_t *));
  121.     if (!newhash)
  122.         return -ENOMEM;

  124.     g->strmask = newmask;
  125.     g->strhash = newhash;
  126.     return 0;
  127. }

  129. /*
  130. * Intern a string and return string object.
  131. */
  132. ‌ktap_str_t * kp_str_new(ktap_state_t *ks, const char *str, size_t len)
  133. {
  134.     ktap_global_state_t *g = G(ks);
  135.     ktap_str_t *s;
  136.     ktap_obj_t *o;
  137.     unsigned int h = kp_str_hash(str, len);
  138.     unsigned long flags;

  140.     if (len >= KP_MAX_STR)
  141.         return NULL;

  143.     local_irq_save(flags);
  144.     arch_spin_lock(&g->str_lock);

  146.     o = (ktap_obj_t *)g->strhash[h & g->strmask];
  147.     if (likely((((uintptr_t)str+len-1) & (PAGE_SIZE-1)) <= PAGE_SIZE-4)) {
  148.         while (o != NULL) {
  149.             ktap_str_t *sx = (ktap_str_t *)o;
  150.             if (sx->len == len &&
  151.                 !str_fastcmp(str, getstr(sx), len)) {
  152.                 arch_spin_unlock(&g->str_lock);
  153.                 local_irq_restore(flags);
  154.                 return sx; /* Return existing string. */
  155.             }
  156.             o = gch(o)->nextgc;
  157.         }
  158.     } else { /* Slow path: end of string is too close to a page boundary */
  159.         while (o != NULL) {
  160.             ktap_str_t *sx = (ktap_str_t *)o;
  161.             if (sx->len == len &&
  162.                 !memcmp(str, getstr(sx), len)) {
  163.                 arch_spin_unlock(&g->str_lock);
  164.                 local_irq_restore(flags);
  165.                 return sx; /* Return existing string. */
  166.             }
  167.             o = gch(o)->nextgc;
  168.         }
  169.     }

  171.     /* create a new string, allocate it from mempool, not use kmalloc. */
  172.     s = kp_mempool_alloc(ks, sizeof(ktap_str_t) + len + 1);
  173.     if (unlikely(!s))
  174.         goto out;
  175.     s->gct = ~KTAP_TSTR;
  176.     s->len = len;
  177.     s->hash = h;
  178.     s->reserved = 0;
  179.     memcpy(s + 1, str, len);
  180.     ((char *)(s + 1))[len] = '\0';  /* ending 0 */

  182.     /* Add it to string hash table */
  183.     h &= g->strmask;
  184.     s->nextgc = (ktap_obj_t *)g->strhash[h];
  185.     g->strhash[h] = s;
  186.     if (g->strnum++ > KP_MAX_STRNUM) {
  187.         kp_error(ks, "exceed max string number %d\n", KP_MAX_STRNUM);
  188.         s = NULL;
  189.     }

  191. out:
  192.     arch_spin_unlock(&g->str_lock);
  193.     local_irq_restore(flags);
  194.     return s; /* Return newly interned string. */
  195. }

  197. ‌void kp_str_freeall(ktap_state_t *ks)
  198. {
  199.     /* don't need to free string in here, it will handled by mempool */
  200.     kp_free(ks, G(ks)->strhash);
  201. }

  203. /* kp_str_fmt - printf implementation */

  205. /* macro to `unsign' a character */
  206. ‌#define uchar(c)    ((unsigned char)(c))

  208. ‌#define L_ESC        '%'

  210. /* valid flags in a format specification */
  211. ‌#define FLAGS    "-+ #0"

  213. ‌#define INTFRMLEN    "ll"
  214. ‌#define INTFRM_T    long long

  216. /*
  217. * maximum size of each format specification (such as '%-099.99d')
  218. * (+10 accounts for %99.99x plus margin of error)
  219. */
  220. ‌#define MAX_FORMAT    (sizeof(FLAGS) + sizeof(INTFRMLEN) + 10)

  222. ‌static const char *scanformat(ktap_state_t *ks, const char *strfrmt, char *form)
  223. {
  224.     const char *p = strfrmt;
  225.     while (*p != '\0' && strchr(FLAGS, *p) != NULL)
  226.         p++;  /* skip flags */

  228.     if ((size_t)(p - strfrmt) >= sizeof(FLAGS)/sizeof(char)) {
  229.         kp_error(ks, "invalid format (repeated flags)\n");
  230.         return NULL;
  231.     }

  233.     if (isdigit(uchar(*p)))
  234.         p++;  /* skip width */

  236.     if (isdigit(uchar(*p)))
  237.         p++;  /* (2 digits at most) */

  239.     if (*p == '.') {
  240.         p++;
  241.         if (isdigit(uchar(*p)))
  242.             p++;  /* skip precision */
  243.         if (isdigit(uchar(*p)))
  244.             p++;  /* (2 digits at most) */
  245.     }

  247.     if (isdigit(uchar(*p))) {
  248.         kp_error(ks, "invalid format (width or precision too long)\n");
  249.         return NULL;
  250.     }

  252.     *(form++) = '%';
  253.     memcpy(form, strfrmt, (p - strfrmt + 1) * sizeof(char));
  254.     form += p - strfrmt + 1;
  255.     *form = '\0';
  256.     return p;
  257. }


  260. /*
  261. * add length modifier into formats
  262. */
  263. ‌static void addlenmod(char *form, const char *lenmod)
  264. {
  265.     size_t l = strlen(form);
  266.     size_t lm = strlen(lenmod);
  267.     char spec = form[l - 1];

  269.     strcpy(form + l - 1, lenmod);
  270.     form[l + lm - 1] = spec;
  271.     form[l + lm] = '\0';
  272. }


  275. ‌static void arg_error(ktap_state_t *ks, int narg, const char *extramsg)
  276. {
  277.     kp_error(ks, "bad argument #%d: (%s)\n", narg, extramsg);
  278. }

  280. ‌int kp_str_fmt(ktap_state_t *ks, struct trace_seq *seq)
  281. {
  282.     int arg = 1;
  283.     size_t sfl;
  284.     ktap_val_t *arg_fmt = kp_arg(ks, 1);
  285.     int argnum = kp_arg_nr(ks);
  286.     const char *strfrmt, *strfrmt_end;

  288.     strfrmt = svalue(arg_fmt);
  289.     sfl = rawtsvalue(arg_fmt)->len;
  290.     strfrmt_end = strfrmt + sfl;

  292.     while (strfrmt < strfrmt_end) {
  293.         if (*strfrmt != L_ESC)
  294.             trace_seq_putc(seq, *strfrmt++);
  295.         else if (*++strfrmt == L_ESC)
  296.             trace_seq_putc(seq, *strfrmt++);
  297.         else { /* format item */
  298.             char form[MAX_FORMAT];

  300.             if (++arg > argnum) {
  301.                 arg_error(ks, arg, "no value");
  302.                 return -1;
  303.             }

  305.             strfrmt = scanformat(ks, strfrmt, form);
  306.             switch (*strfrmt++) {
  307.             case 'c':
  308.                 kp_arg_checknumber(ks, arg);

  310.                 trace_seq_printf(seq, form,
  311.                          nvalue(kp_arg(ks, arg)));
  312.                 break;
  313.             case 'd':  case 'i': {
  314.                 ktap_number n;
  315.                 INTFRM_T ni;

  317.                 kp_arg_checknumber(ks, arg);

  319.                 n = nvalue(kp_arg(ks, arg));
  320.                 ni = (INTFRM_T)n;
  321.                 addlenmod(form, INTFRMLEN);
  322.                 trace_seq_printf(seq, form, ni);
  323.                 break;
  324.             }
  325.             case 'p': {
  326.                 char str[KSYM_SYMBOL_LEN];

  328.                 kp_arg_checknumber(ks, arg);

  330.                 SPRINT_SYMBOL(str, nvalue(kp_arg(ks, arg)));
  331.                 _trace_seq_puts(seq, str);
  332.                 break;
  333.             }
  334.             case 'o':  case 'u':  case 'x':  case 'X': {
  335.                 ktap_number n;
  336.                 unsigned INTFRM_T ni;

  338.                 kp_arg_checknumber(ks, arg);

  340.                 n = nvalue(kp_arg(ks, arg));
  341.                 ni = (unsigned INTFRM_T)n;
  342.                 addlenmod(form, INTFRMLEN);
  343.                 trace_seq_printf(seq, form, ni);
  344.                 break;
  345.             }
  346.             case 's': {
  347.                 ktap_val_t *v = kp_arg(ks, arg);
  348.                 const char *s;
  349.                 size_t l;

  351.                 if (is_nil(v)) {
  352.                     _trace_seq_puts(seq, "nil");
  353.                     return 0;
  354.                 }

  356.                 if (is_eventstr(v)) {
  357.                     const char *str = kp_event_tostr(ks);
  358.                     if (!str)
  359.                         return  -1;
  360.                     _trace_seq_puts(seq,
  361.                         kp_event_tostr(ks));
  362.                     return 0;
  363.                 }

  365.                 kp_arg_checkstring(ks, arg);

  367.                 s = svalue(v);
  368.                 l = rawtsvalue(v)->len;
  369.                 if (!strchr(form, '.') && l >= 100) {
  370.                     /*
  371.                      * no precision and string is too long
  372.                      * to be formatted;
  373.                      * keep original string
  374.                      */
  375.                     _trace_seq_puts(seq, s);
  376.                     break;
  377.                 } else {
  378.                     trace_seq_printf(seq, form, s);
  379.                     break;
  380.                 }
  381.             }
  382.             default: /* also treat cases `pnLlh' */
  383.                 kp_error(ks, "invalid option " KTAP_QL("%%%c")
  384.                          " to " KTAP_QL("format"),
  385.                          *(strfrmt - 1));
  386.                 return -1;
  387.             }
  388.         }
  389.     }

  391.     return 0;
  392. }

One Level Up Top Level