lrotable.c 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180
  1. /* Read-only tables for Lua */
  2. #define LUAC_CROSS_FILE
  3. #include "lua.h"
  4. #include C_HEADER_STRING
  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 16
  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) (519*((size_t)(a)>>4) + 17*((size_t)(b)>>4))
  37. static struct {
  38. unsigned hash;
  39. unsigned addr:24;
  40. unsigned ndx:8;
  41. } cache[LA_LINES][LA_SLOTS];
  42. #ifdef COLLECT_STATS
  43. unsigned cache_stats[3];
  44. #define COUNT(i) cache_stats[i]++
  45. #else
  46. #define COUNT(i)
  47. #endif
  48. static int lookup_cache(unsigned hash, ROTable *rotable) {
  49. int i = (hash>>2) & (LA_LINES-1), j;
  50. for (j = 0; j<LA_SLOTS; j++) {
  51. if (cache[i][j].hash == hash &&
  52. ((size_t)rotable & 0xffffffu) == cache[i][j].addr) {
  53. COUNT(0);
  54. return cache[i][j].ndx;
  55. }
  56. }
  57. COUNT(1);
  58. return -1;
  59. }
  60. static void update_cache(unsigned hash, ROTable *rotable, unsigned ndx) {
  61. int i = (hash)>>2 & (LA_LINES-1), j;
  62. COUNT(2);
  63. if (ndx>0xffu)
  64. return;
  65. for (j = LA_SLOTS-1; j>0; j--)
  66. cache[i][j] = cache[i][j-1];
  67. cache[i][0].hash = hash;
  68. cache[i][0].addr = (size_t) rotable;
  69. cache[i][0].ndx = ndx;
  70. }
  71. /*
  72. * Find a string key entry in a rotable and return it. Note that this internally
  73. * uses a null key to denote a metatable search.
  74. */
  75. const TValue* luaR_findentry(ROTable *rotable, TString *key, unsigned *ppos) {
  76. const luaR_entry *pentry = rotable;
  77. const char *strkey = key ? getstr(key) : ALIGNED_STRING "__metatable" ;
  78. size_t hash = HASH(rotable, key);
  79. unsigned i = 0;
  80. int j = lookup_cache(hash, rotable);
  81. if (pentry) {
  82. if (j >= 0){
  83. if ((pentry[j].key.type == LUA_TSTRING) &&
  84. !c_strcmp(pentry[j].key.id.strkey, strkey)) {
  85. if (ppos)
  86. *ppos = j;
  87. return &pentry[j].value;
  88. }
  89. }
  90. /*
  91. * The invariants for 1st word comparison are deferred to here since they
  92. * aren't needed if there is a cache hit. Note that the termination null
  93. * is included so a "on\0" has a mask of 0xFFFFFF and "a\0" has 0xFFFF.
  94. */
  95. unsigned name4 = *(unsigned *)strkey;
  96. unsigned l = key ? key->tsv.len : sizeof("__metatable")-1;
  97. unsigned mask4 = l > 2 ? (~0u) : (~0u)>>((3-l)*8);
  98. for(;pentry->key.type != LUA_TNIL; i++, pentry++) {
  99. if ((pentry->key.type == LUA_TSTRING) &&
  100. ((*(unsigned *)pentry->key.id.strkey ^ name4) & mask4) == 0 &&
  101. !c_strcmp(pentry->key.id.strkey, strkey)) {
  102. if (ppos)
  103. *ppos = i;
  104. if (j==-1) {
  105. update_cache(hash, rotable, pentry - rotable);
  106. } else if (j != (pentry - rotable)) {
  107. j = 0;
  108. }
  109. return &pentry->value;
  110. }
  111. }
  112. }
  113. return luaO_nilobject;
  114. }
  115. const TValue* luaR_findentryN(ROTable *rotable, luaR_numkey numkey, unsigned *ppos) {
  116. unsigned i = 0;
  117. const luaR_entry *pentry = rotable;
  118. if (pentry) {
  119. for ( ;pentry->key.type != LUA_TNIL; i++, pentry++) {
  120. if (pentry->key.type == LUA_TNUMBER && (luaR_numkey) pentry->key.id.numkey == numkey) {
  121. if (ppos)
  122. *ppos = i;
  123. return &pentry->value;
  124. }
  125. }
  126. }
  127. return NULL;
  128. }
  129. /* Find the metatable of a given table */
  130. void* luaR_getmeta(ROTable *rotable) {
  131. const TValue *res = luaR_findentry(rotable, NULL, NULL);
  132. return res && ttisrotable(res) ? rvalue(res) : NULL;
  133. }
  134. static void luaR_next_helper(lua_State *L, ROTable *pentries, int pos,
  135. TValue *key, TValue *val) {
  136. setnilvalue(key);
  137. setnilvalue(val);
  138. if (pentries[pos].key.type != LUA_TNIL) {
  139. /* Found an entry */
  140. if (pentries[pos].key.type == LUA_TSTRING)
  141. setsvalue(L, key, luaS_new(L, pentries[pos].key.id.strkey))
  142. else
  143. setnvalue(key, (lua_Number)pentries[pos].key.id.numkey)
  144. setobj2s(L, val, &pentries[pos].value);
  145. }
  146. }
  147. /* next (used for iteration) */
  148. void luaR_next(lua_State *L, ROTable *rotable, TValue *key, TValue *val) {
  149. unsigned keypos;
  150. /* Special case: if key is nil, return the first element of the rotable */
  151. if (ttisnil(key))
  152. luaR_next_helper(L, rotable, 0, key, val);
  153. else if (ttisstring(key) || ttisnumber(key)) {
  154. /* Find the previous key again */
  155. if (ttisstring(key)) {
  156. luaR_findentry(rotable, rawtsvalue(key), &keypos);
  157. } else {
  158. luaR_findentryN(rotable, (luaR_numkey)nvalue(key), &keypos);
  159. }
  160. /* Advance to next key */
  161. keypos ++;
  162. luaR_next_helper(L, rotable, keypos, key, val);
  163. }
  164. }