lrotable.c 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168
  1. /* Read-only tables for Lua */
  2. #define LUAC_CROSS_FILE
  3. #include "lua.h"
  4. #include <string.h>
  5. #include "lrotable.h"
  6. #include "lauxlib.h"
  7. #include "lstring.h"
  8. #include "lobject.h"
  9. #include "lapi.h"
  10. #ifdef _MSC_VER
  11. #define ALIGNED_STRING (__declspec( align( 4 ) ) char*)
  12. #else
  13. #define ALIGNED_STRING (__attribute__((aligned(4))) char *)
  14. #endif
  15. #define LA_LINES 32
  16. #define LA_SLOTS 4
  17. //#define COLLECT_STATS
  18. /*
  19. * All keyed ROtable access passes through luaR_findentry(). ROTables
  20. * are simply a list of <key><TValue value> pairs. The existing algo
  21. * did a linear scan of this vector of pairs looking for a match.
  22. *
  23. * A N×M lookaside cache has been added, with a simple hash on the key's
  24. * TString addr and the ROTable addr to identify one of N lines. Each
  25. * line has M slots which are scanned. This is all done in RAM and is
  26. * perhaps 20x faster than the corresponding random Flash accesses which
  27. * will cause flash faults.
  28. *
  29. * If a match is found and the table addresses match, then this entry is
  30. * probed first. In practice the hit-rate here is over 99% so the code
  31. * rarely fails back to doing the linear scan in ROM.
  32. *
  33. * Note that this hash does a couple of prime multiples and a modulus 2^X
  34. * with is all evaluated in H/W, and adequately randomizes the lookup.
  35. */
  36. #define HASH(a,b) (unsigned)((((519*(size_t)(a)))>>4) + ((b) ? (b)->tsv.hash: 0))
  37. typedef struct {
  38. unsigned hash;
  39. unsigned addr:24;
  40. unsigned ndx:8;
  41. } cache_line_t;
  42. static cache_line_t cache [LA_LINES][LA_SLOTS];
  43. #ifdef COLLECT_STATS
  44. unsigned cache_stats[3];
  45. #define COUNT(i) cache_stats[i]++
  46. #else
  47. #define COUNT(i)
  48. #endif
  49. static int lookup_cache(unsigned hash, ROTable *rotable) {
  50. int i = (hash>>2) & (LA_LINES-1), j;
  51. for (j = 0; j<LA_SLOTS; j++) {
  52. cache_line_t cl = cache[i][j];
  53. if (cl.hash == hash && ((size_t)rotable & 0xffffffu) == cl.addr) {
  54. COUNT(0);
  55. return cl.ndx;
  56. }
  57. }
  58. COUNT(1);
  59. return -1;
  60. }
  61. static void update_cache(unsigned hash, ROTable *rotable, unsigned ndx) {
  62. int i = (hash)>>2 & (LA_LINES-1), j;
  63. #ifndef _MSC_VER
  64. cache_line_t cl = {hash, (size_t) rotable, ndx};
  65. #else
  66. cache_line_t cl; // MSC doesn't allow non-scalar initialisers, which
  67. cl.hash = hash; // is a pity because xtensa gcc generates optimum
  68. cl.addr = (size_t) rotable; // code using them.
  69. cl.ndx = ndx;
  70. #endif
  71. COUNT(2);
  72. if (ndx>0xffu)
  73. return;
  74. for (j = LA_SLOTS-1; j>0; j--)
  75. cache[i][j] = cache[i][j-1];
  76. cache[i][0] = cl;
  77. }
  78. /*
  79. * Find a string key entry in a rotable and return it. Note that this internally
  80. * uses a null key to denote a metatable search.
  81. */
  82. const TValue* luaR_findentry(ROTable *rotable, TString *key, unsigned *ppos) {
  83. const luaR_entry *pentry = rotable;
  84. const char *strkey = key ? getstr(key) : ALIGNED_STRING "__metatable" ;
  85. unsigned hash = HASH(rotable, key);
  86. unsigned i = 0;
  87. int j = lookup_cache(hash, rotable);
  88. unsigned l = key ? key->tsv.len : sizeof("__metatable")-1;
  89. if (pentry) {
  90. if (j >= 0 && !strcmp(pentry[j].key, strkey)) {
  91. if (ppos)
  92. *ppos = j;
  93. //dbg_printf("%3d hit %p %s\n", (hash>>2) & (LA_LINES-1), rotable, strkey);
  94. return &pentry[j].value;
  95. }
  96. /*
  97. * The invariants for 1st word comparison are deferred to here since they
  98. * aren't needed if there is a cache hit. Note that the termination null
  99. * is included so a "on\0" has a mask of 0xFFFFFF and "a\0" has 0xFFFF.
  100. */
  101. unsigned name4, mask4 = l > 2 ? (~0u) : (~0u)>>((3-l)*8);
  102. memcpy(&name4, strkey, sizeof(name4));
  103. for(;pentry->key != NULL; i++, pentry++) {
  104. if (((*(unsigned *)pentry->key ^ name4) & mask4) == 0 &&
  105. !strcmp(pentry->key, strkey)) {
  106. //dbg_printf("%p %s hit after %d probes \n", rotable, strkey, (int)(rotable-pentry));
  107. if (ppos)
  108. *ppos = i;
  109. update_cache(hash, rotable, pentry - rotable);
  110. //dbg_printf("%3d %3d %p %s\n", (hash>>2) & (LA_LINES-1), (int)(pentry-rotable), rotable, strkey);
  111. return &pentry->value;
  112. }
  113. }
  114. }
  115. //dbg_printf("%p %s miss after %d probes \n", rotable, strkey, (int)(rotable-pentry));
  116. return luaO_nilobject;
  117. }
  118. /* Find the metatable of a given table */
  119. void* luaR_getmeta(ROTable *rotable) {
  120. const TValue *res = luaR_findentry(rotable, NULL, NULL);
  121. return res && ttisrotable(res) ? rvalue(res) : NULL;
  122. }
  123. static void luaR_next_helper(lua_State *L, ROTable *pentries, int pos,
  124. TValue *key, TValue *val) {
  125. if (pentries[pos].key) {
  126. /* Found an entry */
  127. setsvalue(L, key, luaS_new(L, pentries[pos].key));
  128. setobj2s(L, val, &pentries[pos].value);
  129. } else {
  130. setnilvalue(key);
  131. setnilvalue(val);
  132. }
  133. }
  134. /* next (used for iteration) */
  135. void luaR_next(lua_State *L, ROTable *rotable, TValue *key, TValue *val) {
  136. unsigned keypos;
  137. /* Special case: if key is nil, return the first element of the rotable */
  138. if (ttisnil(key))
  139. luaR_next_helper(L, rotable, 0, key, val);
  140. else if (ttisstring(key)) {
  141. /* Find the previous key again */
  142. if (ttisstring(key)) {
  143. luaR_findentry(rotable, rawtsvalue(key), &keypos);
  144. }
  145. /* Advance to next key */
  146. keypos ++;
  147. luaR_next_helper(L, rotable, keypos, key, val);
  148. }
  149. }