9810946767

Committed 05 Jul 2024 04:05PM UTC coverage: 92.745% (+0.1%) from 92.639%

Build # 9810946767

Build Type

push

github

Committed by

ligurio

Commit Message

FFI: Turn FFI finalizer table into a proper GC root.

Reported by Sergey Bronnikov.

(cherry picked from commit f5affaa6c)

Previous patch fixes the problem partially because the introduced
GC root may not exist at the start phase of the GC cycle. In that
case, the cdata finalizer table will be collected at the end of
the cycle. Access to the cdata finalizer table exhibits heap use
after free. The patch is turned the finalizer table into a proper
GC root.

Sergey Bronnikov:
* added the description and the tests for the problem

Part of tarantool/tarantool#10199

Run Details

5674 of 6025 branches covered (94.17%)

Branch coverage included in aggregate %.

26 of 26 new or added lines in 5 files covered. (100.0%)

313 existing lines in 11 files now uncovered.

21645 of 23431 relevant lines covered (92.38%)

2955369.02 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.74

/src/lj_str.c

/*
** String handling.
** Copyright (C) 2005-2017 Mike Pall. See Copyright Notice in luajit.h
*/

#define lj_str_c
#define LUA_CORE

#include "lj_obj.h"
#include "lj_gc.h"
#include "lj_err.h"
#include "lj_str.h"
#include "lj_char.h"

#if LUAJIT_USE_ASAN
/* These functions may read past a buffer end, that's ok. */
GCstr *lj_str_new(lua_State *L, const char *str, size_t lenx)
  __attribute__((no_sanitize_address));

int32_t LJ_FASTCALL lj_str_cmp(GCstr *a, GCstr *b)
  __attribute__((no_sanitize_address));

static LJ_AINLINE int str_fastcmp(const char *a, const char *b, MSize len)
  __attribute__((no_sanitize_address));
#endif

/* -- String helpers ------------------------------------------------------ */

/* Ordered compare of strings. Assumes string data is 4-byte aligned. */
int32_t LJ_FASTCALL lj_str_cmp(GCstr *a, GCstr *b)
{
  MSize i, n = a->len > b->len ? b->len : a->len;
  for (i = 0; i < n; i += 4) {
    /* Note: innocuous access up to end of string + 3. */
    uint32_t va = *(const uint32_t *)(strdata(a)+i);
    uint32_t vb = *(const uint32_t *)(strdata(b)+i);
    if (va != vb) {
#if LJ_LE
      va = lj_bswap(va); vb = lj_bswap(vb);
#endif
      i -= n;
      if ((int32_t)i >= -3) {
        va >>= 32+(i<<3); vb >>= 32+(i<<3);
        if (va == vb) break;
      }
      return va < vb ? -1 : 1;
    }
  }
  return (int32_t)(a->len - b->len);
}

/* Fast string data comparison. Caveat: unaligned access to 1st string! */
static LJ_AINLINE int str_fastcmp(const char *a, const char *b, MSize len)
{
  MSize i = 0;
  lj_assertX(len > 0, "fast string compare with zero length");
  lj_assertX((((uintptr_t)a+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4,
             "fast string compare crossing page boundary");
  do {  /* Note: innocuous access up to end of string + 3. */
    uint32_t v = lj_getu32(a+i) ^ *(const uint32_t *)(b+i);
    if (v) {
      i -= len;
#if LJ_LE
      return (int32_t)i >= -3 ? (v << (32+(i<<3))) : 1;
#else
      return (int32_t)i >= -3 ? (v >> (32+(i<<3))) : 1;
#endif
    }
    i += 4;
  } while (i < len);
  return 0;
}

/* Find fixed string p inside string s. */
const char *lj_str_find(const char *s, const char *p, MSize slen, MSize plen)
{
  if (plen <= slen) {
    if (plen == 0) {
      return s;
    } else {
      int c = *(const uint8_t *)p++;
      plen--; slen -= plen;
      while (slen) {
        const char *q = (const char *)memchr(s, c, slen);
        if (!q) break;
        if (memcmp(q+1, p, plen) == 0) return q;
        q++; slen -= (MSize)(q-s); s = q;
      }
    }
  }
  return NULL;
}

/* Check whether a string has a pattern matching character. */
int lj_str_haspattern(GCstr *s)
{
  const char *p = strdata(s), *q = p + s->len;
  while (p < q) {
    int c = *(const uint8_t *)p++;
    if (lj_char_ispunct(c) && strchr("^$*+?.([%-", c))
      return 1;  /* Found a pattern matching char. */
  }
  return 0;  /* No pattern matching chars found. */
}

/* -- String interning ---------------------------------------------------- */

/* Resize the string hash table (grow and shrink). */
void lj_str_resize(lua_State *L, MSize newmask)
{
  global_State *g = G(L);
  GCRef *newhash;
  MSize i;
  if (g->gc.state == GCSsweepstring || newmask >= LJ_MAX_STRTAB-1)
    return;  /* No resizing during GC traversal or if already too big. */
  newhash = lj_mem_newvec(L, newmask+1, GCRef);
  memset(newhash, 0, (newmask+1)*sizeof(GCRef));
  for (i = g->strmask; i != ~(MSize)0; i--) {  /* Rehash old table. */
    GCobj *p = gcref(g->strhash[i]);
    while (p) {  /* Follow each hash chain and reinsert all strings. */
      MSize h = gco2str(p)->hash & newmask;
      GCobj *next = gcnext(p);
      /* NOBARRIER: The string table is a GC root. */
      setgcrefr(p->gch.nextgc, newhash[h]);
      setgcref(newhash[h], p);
      p = next;
    }
  }
  lj_mem_freevec(g, g->strhash, g->strmask+1, GCRef);
  g->strmask = newmask;
  g->strhash = newhash;
}

#if LUAJIT_SMART_STRINGS
static LJ_AINLINE uint32_t
lj_fullhash(const uint8_t *v, MSize len)
{
  MSize a = 0, b = 0;
  MSize c = 0xcafedead;
  MSize d = 0xdeadbeef;
  MSize h = len;
  lj_assertX(len >= 12, "full hash calculation for too short (%d) string", len);
  for(; len>8; len-=8, v+=8) {
    a ^= lj_getu32(v);
    b ^= lj_getu32(v+4);
    c += a;
    d += b;
    a = lj_rol(a, 5) - d;
    b = lj_rol(b, 7) - c;
    c = lj_rol(c, 24) ^ a;
    d = lj_rol(d, 1) ^ b;
  }
  a ^= lj_getu32(v+len-8);
  b ^= lj_getu32(v+len-4);
  c += b; c -= lj_rol(a, 9);
  d += a; d -= lj_rol(b, 18);
  h -= lj_rol(a^b,7);
  h += c; h += lj_rol(d,13);
  d ^= c;  d -= lj_rol(c,25);
  h ^= d; h -= lj_rol(d,16);
  c ^= h; c -= lj_rol(h,4);
  d ^= c;  d -= lj_rol(c,14);
  h ^= d; h -= lj_rol(d,24);
  return h;
}
#endif

/* Intern a string and return string object. */
GCstr *lj_str_new(lua_State *L, const char *str, size_t lenx)
{
  global_State *g;
  GCstr *s;
  GCobj *o;
  MSize len = (MSize)lenx;
  uint8_t strflags = 0;
#if LUAJIT_SMART_STRINGS
  unsigned collisions = 0;
#endif
  if (lenx >= LJ_MAX_STR)
    lj_err_msg(L, LJ_ERR_STROV);
  g = G(L);
  if (len == 0)
    return &g->strempty;
  /* Compute string hash. Constants taken from lookup3 hash by Bob Jenkins. */
  MSize h = lua_hash(str, len);
  /* Check if the string has already been interned. */
  o = gcref(g->strhash[h & g->strmask]);
#if LUAJIT_SMART_STRINGS
/*
** The default "fast" string hash function samples only a few positions
** in a string, the remaining bytes don't affect the function's result.
** The function performs well for short strings; however long strings
** can yield extremely high collision rates.
**
** An adaptive schema was implemented. Two hash functions are used
** simultaneously. A bucket is picked based on the output of the fast
** hash function. If an item is to be inserted in a collision chain
** longer than a certain threshold, another bucket is picked based on
** the stronger hash function. Since two hash functions are used
** simultaneously, insert should consider two buckets. The second bucket
** is often NOT considered thanks to the bloom filter. The filter is
** rebuilt during GC cycle.
**
** Parameters below were tuned on a set of benchmarks. Max_collisions is
** also backed by theory: the expected maximum length of a collision
** chain in a hash table with the fill factor of 1.0 is
** O(log(N)/log(log(N))), assuming uniformly distributed random keys.
** The upper bound for N=65,000 is 10, hence 40 is a clear indication of
** an anomaly.
**/
#define max_collisions 40
#define inc_collision_soft() (collisions++)
/* If different strings yield the same hash sum, grow counter faster. */
#define inc_collision_hard() (collisions+=1+(len>>4), 1)
#else
#define inc_collision_hard() (1)
#define inc_collision_soft()
#endif
  if (LJ_LIKELY((((uintptr_t)str+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4)) {
    while (o != NULL) {
      GCstr *sx = gco2str(o);
      if (sx->hash == h && sx->len == len && inc_collision_hard() &&
                      str_fastcmp(str, strdata(sx), len) == 0) {
        /* Resurrect if dead. Can only happen with fixstring() (keywords). */
        if (isdead(g, o)) flipwhite(o);
        g->strhash_hit++;
        return sx;  /* Return existing string. */
      }
      o = gcnext(o);
      inc_collision_soft();
    }
  } else {  /* Slow path: end of string is too close to a page boundary. */
    while (o != NULL) {
      GCstr *sx = gco2str(o);
      if (sx->hash == h && sx->len == len && inc_collision_hard() &&
                      memcmp(str, strdata(sx), len) == 0) {
        /* Resurrect if dead. Can only happen with fixstring() (keywords). */
        if (isdead(g, o)) flipwhite(o);
        g->strhash_hit++;
        return sx;  /* Return existing string. */
      }
      o = gcnext(o);
      inc_collision_soft();
    }
  }
#if LUAJIT_SMART_STRINGS
  /* "Fast" hash function consumes all bytes of a string <= 12 bytes. */
  if (len > 12) {
    /*
    ** The bloom filter is keyed with the high 12 bits of the fast
    ** hash sum. The filter is rebuilt during GC cycle. It's beneficial
    ** to have these bits readily available and avoid hash sum
    ** recalculation during GC. High 6 bits are included in the "full"
    ** hash sum, and bits 19-25 are stored in s->strflags.
    **/
    int search_fullh =
       bloomtest(g->strbloom.cur[0], h>>(sizeof(h)*8- 6)) != 0 &&
       bloomtest(g->strbloom.cur[1], h>>(sizeof(h)*8-12)) != 0;
    if (LJ_UNLIKELY(search_fullh || collisions > max_collisions)) {
      MSize fh = lj_fullhash((const uint8_t*)str, len);
#define high6mask ((~(MSize)0)<<(sizeof(MSize)*8-6))
      fh = (fh >> 6) | (h & high6mask);
      if (search_fullh) {
        /* Recheck if the string has already been interned with "harder" hash. */
        o = gcref(g->strhash[fh & g->strmask]);
        if (LJ_LIKELY((((uintptr_t)str+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4)) {
          while (o != NULL) {
            GCstr *sx = gco2str(o);
            if (sx->hash == fh && sx->len == len && str_fastcmp(str, strdata(sx), len) == 0) {
              /* Resurrect if dead. Can only happen with fixstring() (keywords). */
              if (isdead(g, o)) flipwhite(o);
              g->strhash_hit++;
              return sx;  /* Return existing string. */
            }
            o = gcnext(o);
          }
        } else {  /* Slow path: end of string is too close to a page boundary. */
          while (o != NULL) {
            GCstr *sx = gco2str(o);
            if (sx->hash == fh && sx->len == len && memcmp(str, strdata(sx), len) == 0) {
              /* Resurrect if dead. Can only happen with fixstring() (keywords). */
              if (isdead(g, o)) flipwhite(o);
              g->strhash_hit++;
              return sx;  /* Return existing string. */
            }
            o = gcnext(o);
          }
        }
      }
      if (collisions > max_collisions) {
        strflags = 0xc0 | ((h>>(sizeof(h)*8-12))&0x3f);
        bloomset(g->strbloom.cur[0], h>>(sizeof(h)*8- 6));
        bloomset(g->strbloom.cur[1], h>>(sizeof(h)*8-12));
        bloomset(g->strbloom.next[0], h>>(sizeof(h)*8- 6));
        bloomset(g->strbloom.next[1], h>>(sizeof(h)*8-12));
        h = fh;
      }
    }
  }
#endif
  g->strhash_miss++;
  /* Nope, create a new string. */
  s = lj_mem_newt(L, sizeof(GCstr)+len+1, GCstr);
  newwhite(g, s);
  s->gct = ~LJ_TSTR;
  s->len = len;
  s->hash = h;
  s->reserved = 0;
  s->strflags = strflags;
  memcpy(strdatawr(s), str, len);
  strdatawr(s)[len] = '\0';  /* Zero-terminate string. */
  /* Add it to string hash table. */
  h &= g->strmask;
  s->nextgc = g->strhash[h];
  /* NOBARRIER: The string table is a GC root. */
  setgcref(g->strhash[h], obj2gco(s));
  if (g->strnum++ > g->strmask)  /* Allow a 100% load factor. */
    lj_str_resize(L, (g->strmask<<1)+1);  /* Grow string table. */
  return s;  /* Return newly interned string. */
}

void LJ_FASTCALL lj_str_free(global_State *g, GCstr *s)
{
  g->strnum--;
  lj_mem_free(g, s, sizestring(s));
}


1	/*
2	** String handling.
3	** Copyright (C) 2005-2017 Mike Pall. See Copyright Notice in luajit.h
4	*/
5
6	#define lj_str_c
7	#define LUA_CORE
8
9	#include "lj_obj.h"
10	#include "lj_gc.h"
11	#include "lj_err.h"
12	#include "lj_str.h"
13	#include "lj_char.h"
14
15	#if LUAJIT_USE_ASAN
16	/* These functions may read past a buffer end, that's ok. */
17	GCstr lj_str_new(lua_State L, const char *str, size_t lenx)
18	__attribute__((no_sanitize_address));
19
20	int32_t LJ_FASTCALL lj_str_cmp(GCstr a, GCstr b)
21	__attribute__((no_sanitize_address));
22
23	static LJ_AINLINE int str_fastcmp(const char a, const char b, MSize len)
24	__attribute__((no_sanitize_address));
25	#endif
26
27	/* -- String helpers ------------------------------------------------------ */
28
29	/* Ordered compare of strings. Assumes string data is 4-byte aligned. */
30	int32_t LJ_FASTCALL lj_str_cmp(GCstr a, GCstr b)	103,370✔
31	{
32	MSize i, n = a->len > b->len ? b->len : a->len;	103,370✔
33	for (i = 0; i < n; i += 4) {	109,870✔
34	/* Note: innocuous access up to end of string + 3. */
35	uint32_t va = (const uint32_t )(strdata(a)+i);	103,472✔
36	uint32_t vb = (const uint32_t )(strdata(b)+i);	103,472✔
37	if (va != vb) {	103,472✔
38	#if LJ_LE
39	va = lj_bswap(va); vb = lj_bswap(vb);	96,972✔
40	#endif
41	i -= n;	96,972✔
42	if ((int32_t)i >= -3) {	96,972✔
43	va >>= 32+(i<<3); vb >>= 32+(i<<3);	96,789✔
44	if (va == vb) break;	96,789✔
45	}
46	return va < vb ? -1 : 1;	96,508✔
47	}
48	}
49	return (int32_t)(a->len - b->len);	6,862✔
50	}
51
52	/* Fast string data comparison. Caveat: unaligned access to 1st string! */
53	static LJ_AINLINE int str_fastcmp(const char a, const char b, MSize len)	8,697,242✔
54	{
55	MSize i = 0;	8,697,242✔
56	lj_assertX(len > 0, "fast string compare with zero length");	16,706,466✔
57	lj_assertX((((uintptr_t)a+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4,	16,706,466✔
58	"fast string compare crossing page boundary");
59	do { /* Note: innocuous access up to end of string + 3. */	16,706,466✔
60	uint32_t v = lj_getu32(a+i) ^ (const uint32_t )(b+i);	16,706,466✔
61	if (v) {	16,706,466✔
62	i -= len;	3,137,897✔
63	#if LJ_LE
64	return (int32_t)i >= -3 ? (v << (32+(i<<3))) : 1;	3,137,897✔
65	#else
66	return (int32_t)i >= -3 ? (v >> (32+(i<<3))) : 1;
67	#endif
68	}
69	i += 4;	13,568,569✔
70	} while (i < len);	13,568,569✔
71	return 0;
72	}
73
74	/* Find fixed string p inside string s. */
75	const char lj_str_find(const char s, const char *p, MSize slen, MSize plen)	2,570✔
76	{
77	if (plen <= slen) {	2,570✔
78	if (plen == 0) {	2,497✔
79	return s;
80	} else {
81	int c = (const uint8_t )p++;	2,494✔
82	plen--; slen -= plen;	2,494✔
83	while (slen) {	8,540✔
84	const char q = (const char )memchr(s, c, slen);	8,458✔
85	if (!q) break;	8,458✔
86	if (memcmp(q+1, p, plen) == 0) return q;	6,323✔
87	q++; slen -= (MSize)(q-s); s = q;	6,046✔
88	}
89	}
90	}
91	return NULL;
92	}
93
94	/* Check whether a string has a pattern matching character. */
95	int lj_str_haspattern(GCstr *s)	2,514✔
96	{
97	const char p = strdata(s), q = p + s->len;	2,514✔
98	while (p < q) {	5,668✔
99	int c = (const uint8_t )p++;	4,333✔
100	if (lj_char_ispunct(c) && strchr("^$*+?.([%-", c))	4,333✔
101	return 1; /* Found a pattern matching char. */
102	}
103	return 0; /* No pattern matching chars found. */
104	}
105
106	/* -- String interning ---------------------------------------------------- */
107
108	/* Resize the string hash table (grow and shrink). */
109	void lj_str_resize(lua_State *L, MSize newmask)	955✔
110	{
111	global_State *g = G(L);	955✔
112	GCRef *newhash;	955✔
113	MSize i;	955✔
114	if (g->gc.state == GCSsweepstring \|\| newmask >= LJ_MAX_STRTAB-1)	955✔
115	return; /* No resizing during GC traversal or if already too big. */
116	newhash = lj_mem_newvec(L, newmask+1, GCRef);	955✔
117	memset(newhash, 0, (newmask+1)*sizeof(GCRef));	955✔
118	for (i = g->strmask; i != ~(MSize)0; i--) { /* Rehash old table. */	1,849,275✔
119	GCobj *p = gcref(g->strhash[i]);	1,848,320✔
120	while (p) { /* Follow each hash chain and reinsert all strings. */	2,684,347✔
121	MSize h = gco2str(p)->hash & newmask;	836,027✔
122	GCobj *next = gcnext(p);	836,027✔
123	/* NOBARRIER: The string table is a GC root. */
124	setgcrefr(p->gch.nextgc, newhash[h]);	836,027✔
125	setgcref(newhash[h], p);	836,027✔
126	p = next;	836,027✔
127	}
128	}
129	lj_mem_freevec(g, g->strhash, g->strmask+1, GCRef);	955✔
130	g->strmask = newmask;	955✔
131	g->strhash = newhash;	955✔
132	}
133
134	#if LUAJIT_SMART_STRINGS
135	static LJ_AINLINE uint32_t
136	lj_fullhash(const uint8_t *v, MSize len)
137	{
138	MSize a = 0, b = 0;
139	MSize c = 0xcafedead;
140	MSize d = 0xdeadbeef;
141	MSize h = len;	3,019,348✔
142	lj_assertX(len >= 12, "full hash calculation for too short (%d) string", len);
143	for(; len>8; len-=8, v+=8) {	3,019,348✔
144	a ^= lj_getu32(v);	2,975,651✔
145	b ^= lj_getu32(v+4);	2,975,651✔
146	c += a;	2,975,651✔
147	d += b;	2,975,651✔
148	a = lj_rol(a, 5) - d;	2,975,651✔
149	b = lj_rol(b, 7) - c;	2,975,651✔
150	c = lj_rol(c, 24) ^ a;	2,975,651✔
151	d = lj_rol(d, 1) ^ b;	2,975,651✔
152	}
153	a ^= lj_getu32(v+len-8);	43,697✔
154	b ^= lj_getu32(v+len-4);	43,697✔
155	c += b; c -= lj_rol(a, 9);	43,697✔
156	d += a; d -= lj_rol(b, 18);	43,697✔
157	h -= lj_rol(a^b,7);	43,697✔
158	h += c; h += lj_rol(d,13);	43,697✔
159	d ^= c; d -= lj_rol(c,25);	43,697✔
160	h ^= d; h -= lj_rol(d,16);	43,697✔
161	c ^= h; c -= lj_rol(h,4);	43,697✔
162	d ^= c; d -= lj_rol(c,14);	43,697✔
163	h ^= d; h -= lj_rol(d,24);	43,697✔
164	return h;	43,697✔
165	}
166	#endif
167
168	/* Intern a string and return string object. */
169	GCstr lj_str_new(lua_State L, const char *str, size_t lenx)	9,301,605✔
170	{
171	global_State *g;	9,301,605✔
172	GCstr *s;	9,301,605✔
173	GCobj *o;	9,301,605✔
174	MSize len = (MSize)lenx;	9,301,605✔
175	uint8_t strflags = 0;	9,301,605✔
176	#if LUAJIT_SMART_STRINGS
177	unsigned collisions = 0;	9,301,605✔
178	#endif
179	if (lenx >= LJ_MAX_STR)	9,301,605✔
180	lj_err_msg(L, LJ_ERR_STROV);	×
181	g = G(L);	9,301,605✔
182	if (len == 0)	9,301,605✔
183	return &g->strempty;	5,538✔
184	/* Compute string hash. Constants taken from lookup3 hash by Bob Jenkins. */
185	MSize h = lua_hash(str, len);	9,296,067✔
186	/* Check if the string has already been interned. */
187	o = gcref(g->strhash[h & g->strmask]);	9,296,067✔
188	#if LUAJIT_SMART_STRINGS
189	/*
190	** The default "fast" string hash function samples only a few positions
191	** in a string, the remaining bytes don't affect the function's result.
192	** The function performs well for short strings; however long strings
193	** can yield extremely high collision rates.
194	**
195	** An adaptive schema was implemented. Two hash functions are used
196	** simultaneously. A bucket is picked based on the output of the fast
197	** hash function. If an item is to be inserted in a collision chain
198	** longer than a certain threshold, another bucket is picked based on
199	** the stronger hash function. Since two hash functions are used
200	** simultaneously, insert should consider two buckets. The second bucket
201	** is often NOT considered thanks to the bloom filter. The filter is
202	** rebuilt during GC cycle.
203	**
204	** Parameters below were tuned on a set of benchmarks. Max_collisions is
205	** also backed by theory: the expected maximum length of a collision
206	** chain in a hash table with the fill factor of 1.0 is
207	** O(log(N)/log(log(N))), assuming uniformly distributed random keys.
208	** The upper bound for N=65,000 is 10, hence 40 is a clear indication of
209	** an anomaly.
210	**/
211	#define max_collisions 40
212	#define inc_collision_soft() (collisions++)
213	/* If different strings yield the same hash sum, grow counter faster. */
214	#define inc_collision_hard() (collisions+=1+(len>>4), 1)
215	#else
216	#define inc_collision_hard() (1)
217	#define inc_collision_soft()
218	#endif
219	if (LJ_LIKELY((((uintptr_t)str+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4)) {	9,296,067✔
220	while (o != NULL) {	13,453,166✔
221	GCstr *sx = gco2str(o);	12,661,582✔
222	if (sx->hash == h && sx->len == len && inc_collision_hard() &&	12,661,582✔
223	str_fastcmp(str, strdata(sx), len) == 0) {	17,175,817✔
224	/* Resurrect if dead. Can only happen with fixstring() (keywords). */
225	if (isdead(g, o)) flipwhite(o);	8,498,147✔
226	g->strhash_hit++;	8,498,147✔
227	return sx; /* Return existing string. */	8,498,147✔
228	}
229	o = gcnext(o);	4,163,435✔
230	inc_collision_soft();	4,163,435✔
231	}
232	} else { /* Slow path: end of string is too close to a page boundary. */
233	while (o != NULL) {	7,459✔
234	GCstr *sx = gco2str(o);	7,265✔
235	if (sx->hash == h && sx->len == len && inc_collision_hard() &&	7,265✔
236	memcmp(str, strdata(sx), len) == 0) {	6,145✔
237	/* Resurrect if dead. Can only happen with fixstring() (keywords). */
238	if (isdead(g, o)) flipwhite(o);	6,142✔
239	g->strhash_hit++;	6,142✔
240	return sx; /* Return existing string. */	6,142✔
241	}
242	o = gcnext(o);	1,123✔
243	inc_collision_soft();	1,123✔
244	}
245	}
246	#if LUAJIT_SMART_STRINGS
247	/* "Fast" hash function consumes all bytes of a string <= 12 bytes. */
248	if (len > 12) {	791,778✔
249	/*
250	** The bloom filter is keyed with the high 12 bits of the fast
251	** hash sum. The filter is rebuilt during GC cycle. It's beneficial
252	** to have these bits readily available and avoid hash sum
253	** recalculation during GC. High 6 bits are included in the "full"
254	** hash sum, and bits 19-25 are stored in s->strflags.
255	**/
256	int search_fullh =	439,438✔
257	bloomtest(g->strbloom.cur[0], h>>(sizeof(h)*8- 6)) != 0 &&	219,719✔
258	bloomtest(g->strbloom.cur[1], h>>(sizeof(h)*8-12)) != 0;	52,374✔
259	if (LJ_UNLIKELY(search_fullh \|\| collisions > max_collisions)) {	219,719✔
260	MSize fh = lj_fullhash((const uint8_t*)str, len);	43,697✔
261	#define high6mask ((~(MSize)0)<<(sizeof(MSize)*8-6))
262	fh = (fh >> 6) \| (h & high6mask);	43,697✔
263	if (search_fullh) {	43,697✔
264	/* Recheck if the string has already been interned with "harder" hash. */
265	o = gcref(g->strhash[fh & g->strmask]);	42,383✔
266	if (LJ_LIKELY((((uintptr_t)str+len-1) & (LJ_PAGESIZE-1)) <= LJ_PAGESIZE-4)) {	42,383✔
267	while (o != NULL) {	56,959✔
268	GCstr *sx = gco2str(o);	34,148✔
269	if (sx->hash == fh && sx->len == len && str_fastcmp(str, strdata(sx), len) == 0) {	53,720✔
270	/* Resurrect if dead. Can only happen with fixstring() (keywords). */
271	if (isdead(g, o)) flipwhite(o);	19,572✔
272	g->strhash_hit++;	19,572✔
273	return sx; /* Return existing string. */	19,572✔
274	}
275	o = gcnext(o);	14,576✔
276	}
277	} else { /* Slow path: end of string is too close to a page boundary. */
UNCOV 278	while (o != NULL) {	×
UNCOV 279	GCstr *sx = gco2str(o);	×
UNCOV 280	if (sx->hash == fh && sx->len == len && memcmp(str, strdata(sx), len) == 0) {	×
281	/* Resurrect if dead. Can only happen with fixstring() (keywords). */
UNCOV 282	if (isdead(g, o)) flipwhite(o);	×
UNCOV 283	g->strhash_hit++;	×
UNCOV 284	return sx; /* Return existing string. */	×
285	}
286	o = gcnext(o);	×
287	}
288	}
289	}
290	if (collisions > max_collisions) {	24,125✔
291	strflags = 0xc0 \| ((h>>(sizeof(h)*8-12))&0x3f);	21,211✔
292	bloomset(g->strbloom.cur[0], h>>(sizeof(h)*8- 6));	21,211✔
293	bloomset(g->strbloom.cur[1], h>>(sizeof(h)*8-12));	21,211✔
294	bloomset(g->strbloom.next[0], h>>(sizeof(h)*8- 6));	21,211✔
295	bloomset(g->strbloom.next[1], h>>(sizeof(h)*8-12));	21,211✔
296	h = fh;	21,211✔
297	}
298	}
299	}
300	#endif
301	g->strhash_miss++;	772,206✔
302	/* Nope, create a new string. */
303	s = lj_mem_newt(L, sizeof(GCstr)+len+1, GCstr);	772,206✔
304	newwhite(g, s);	772,206✔
305	s->gct = ~LJ_TSTR;	772,206✔
306	s->len = len;	772,206✔
307	s->hash = h;	772,206✔
308	s->reserved = 0;	772,206✔
309	s->strflags = strflags;	772,206✔
310	memcpy(strdatawr(s), str, len);	772,206✔
311	strdatawr(s)[len] = '\0'; /* Zero-terminate string. */	772,206✔
312	/* Add it to string hash table. */
313	h &= g->strmask;	772,206✔
314	s->nextgc = g->strhash[h];	772,206✔
315	/* NOBARRIER: The string table is a GC root. */
316	setgcref(g->strhash[h], obj2gco(s));	772,206✔
317	if (g->strnum++ > g->strmask) /* Allow a 100% load factor. */	772,206✔
318	lj_str_resize(L, (g->strmask<<1)+1); /* Grow string table. */	524✔
319	return s; /* Return newly interned string. */
320	}
321
322	void LJ_FASTCALL lj_str_free(global_State g, GCstr s)	767,931✔
323	{
324	g->strnum--;	767,931✔
325	lj_mem_free(g, s, sizestring(s));	767,931✔
326	}	767,931✔
327

tarantool / luajit / 9810946767

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous