lua string 源码浅析
是这样的，早之前是准备分析下这块的，因为从C/C++转到写lua，虽然上手很容易但是用好不容易，我见过好些业务代码写的其实一般般，不会过多考虑到更深层次的问题。当然，用lua肯定是出于某些业务方面的考虑，大部分不需要考虑底层实现。比如招写C++同学的很难，不小心就线上宕机不可控，再然后线上的热更新不大好支持，需要热重启，或者出现死循环这种怎么跳出来等等。
选择某种框架和开发语言，有当时的业务背景，所以怎么合适怎么来，没有必要感觉这种技术很low什么的。很多项目最后都没机会上线，所以这里分清主次。另外，框架这种设计因素较多这里不再说明，自己知道就行。
这里总结下这个月的工作情况。这一月份开始事情就不多了，很少新的需求，大部分时间是优化新项目用到的基础代码，没错，一七年底准备新项目我也在优化，虽然效果还不错，但并不满意，有几个古老的实现不能动。新项目这里我优化的模块跟具体业务需求没什么关系，毕竟现在还没有到这个地步，只是把基础的高频次使用的实现再次review。月初优化过相关的实现，服务器这边性能提高15-22%，客户端提升大概8%，后来增加某种技巧，使得很大程度上减小开销，这块后来消耗为零。新项目增加了碰撞检测功能，是用C++实现的，当然我也发现了内存泄露，C++中的泄露在LUA层是无法统计出来的。验证的话是容易，只要加快复现，因为原代码中每次new的是小对象，修改也容易，只不过让当初写这块的同学改了。优化了战斗中某些接口，因为是高频次调用，优化后比原来快4~5倍，当然和C/C++是无法比的，优化的事情还是要继续做，这种一般借助工具或经验，对于我来说，每写相关的实现和review其他同学写的功能，就知道大概性能如何。
这应该说是我在今年一月份做的比较有意义的两件事情，一个是优化定时器，性能有一定的提升，二是发现新项目的内存泄漏，和多余的性能开销。
lua语言是值得研究和学习的，我也考虑过这个事情，无奈时间安排不过来，只是在工作中用到基本的，没有深入其他一些源码实现。虽然平时主要写需求，但常用的还是字符串和表等这几种数据结构，怎么用和用好，还是要了解下怎么实现的，这里，以使用为出发点来简单介绍下string的实现，可能我分析的不够清晰和深入，有兴趣可以自己看下源码，至于代码怎么写，还是要注意下，先把功能写对，再profile找热点再优化。
对于lua的其他字符串的相关实现这里不再分析，有点杂，等使用到的时候有热点时再分析，当然还是减少那种关于字符串匹配查找替换等的操作。
这里分析的代码直接是lstring中的，有些太细节和全局性的实现跳过，后期有时间再一一分析。
字符串结构：
299 /*
300 ** Header for string value; string bytes follow the end of this structure
301 ** (aligned according to 'UTString'; see next).
302 */
303 typedef struct TString {
304 CommonHeader;
305 lu_byte extra; /* reserved words for short strings; "has hash" for longs */
306 lu_byte shrlen; /* length for short strings */
307 unsigned int hash;
308 union {
309 size_t lnglen; /* length for long strings */
310 struct TString *hnext; /* linked list for hash table */
311 } u;
312 } TString;
创建一个新的字符串：
230 /*
231 ** Create or reuse a zero-terminated string, first checking in the
232 ** cache (using the string address as a key). The cache can contain
233 ** only zero-terminated strings, so it is safe to use 'strcmp' to
234 ** check hits.
235 */
236 TString *luaS_new (lua_State *L, const char *str) {
237 unsigned int i = point2uint(str) % STRCACHE_N; /* hash */
238 int j;
239 TString **p = G(L)->strcache[i];
240 for (j = 0; j < STRCACHE_M; j++) {
241 if (strcmp(str, getstr(p[j])) == 0) /* hit? */
242 return p[j]; /* that is it */
243 }
244 /* normal route */
245 for (j = STRCACHE_M - 1; j > 0; j--)
246 p[j] = p[j - 1]; /* move out last element */
247 /* new element is first in the list */
248 p[0] = luaS_newlstr(L, str, strlen(str));
249 return p[0];
250 }
以上会先从53*2的二维数组cache中查找是否已存在相同的string，有的话直接返回并不创建新的。否则创建新的并cache：
213 /*
214 ** new string (with explicit length)
215 */
216 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
217 if (l <= LUAI_MAXSHORTLEN) /* short string? */
218 return internshrstr(L, str, l);
219 else {
220 TString *ts;
221 if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char))
222 luaM_toobig(L);
223 ts = luaS_createlngstrobj(L, l);
224 memcpy(getstr(ts), str, l * sizeof(char));
225 return ts;
226 }
227 }
对于长度小于等于40的string来说，可能是直接通过hash查找并复用，并不会直接创建：
525 static TString *
526 internshrstr (lua_State *L, const char *str, size_t l) {
527 TString *ts;
528 global_State *g = G(L);
529 unsigned int h = luaS_hash(str, l, g->seed);
530 unsigned int h0;
531 // lookup global state of this L first
532 ts = queryshrstr (L, str, l, h);
533 if (ts)
534 return ts;
535 // lookup SSM again
536 h0 = luaS_hash(str, l, 0);
537 ts = query_string(NULL, h0, str, l);
538 if (ts)
539 return ts;
540 // If SSM.n greate than 0, add it to SSM
541 if (SSM.n > 0) {
542 ATOM_DEC(&SSM.n);
543 return add_string(h0, str, l);
544 }
545 // Else add it to global state (local)
546 return addshrstr (L, str, l, h);
547 }
174 /*
175 ** checks whether short string exists and reuses it or creates a new one
176 */
177 static TString *queryshrstr (lua_State *L, const char *str, size_t l, unsigned int h) {
178 TString *ts;
179 global_State *g = G(L);
180 TString **list = &g->strt.hash[lmod(h, g->strt.size)];
181 lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */
182 for (ts = *list; ts != NULL; ts = ts->u.hnext) {
183 if (l == ts->shrlen &&
184 (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
185 /* found! */
186 if (isdead(g, ts)) /* dead (but not collected yet)? */
187 changewhite(ts); /* resurrect it */
188 return ts;
189 }
190 }
191 return NULL;
192 }
以上查找会查两遍，这里query_string会加锁rwlock_rlock这些，接着add_string：
504 static TString *
505 add_string(unsigned int h, const char *str, lu_byte l) {
506 struct shrmap * s = &SSM;
507 TString * tmp = new_string(h, str, l);
508 rwlock_rlock(&s->lock);
509 struct TString *ts = shrstr_exist(s, h, str, l);
510 if (ts) {
511 // string is create by other thread, so free tmp
512 free(tmp);
513 } else {
514 struct shrmap_slot *slot = &s->readwrite[h & s->mask];
515 ts = tmp;
516 ts->u.hnext = slot->str;
517 slot->str = ts;
518 rwlock_wunlock(&slot->lock);
519 ATOM_INC(&SSM.total);
520 }
521 rwlock_runlock(&s->lock);
522 return ts;
523 }
若都没的话则创建addshrstr：
194 static TString *addshrstr (lua_State *L, const char *str, size_t l, unsigned int h) {
195 TString *ts;
196 global_State *g = G(L);
197 TString **list = &g->strt.hash[lmod(h, g->strt.size)];
198 if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) {
199 luaS_resize(L, g->strt.size * 2);
200 list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */
201 }
202 ts = createstrobj(L, l, LUA_TSHRSTR, h);
203 memcpy(getstr(ts), str, l * sizeof(char));
204 ts->shrlen = cast_byte(l);
205 ts->u.hnext = *list;
206 *list = ts;
207 g->strt.nuse++;
208 return ts;
209 }
130 /*
131 ** creates a new string object
132 */
133 static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
134 TString *ts;
135 GCObject *o;
136 size_t totalsize; /* total size of TString object */
137 totalsize = sizelstring(l);
138 o = luaC_newobj(L, tag, totalsize);
139 ts = gco2ts(o);
140 ts->hash = h;
141 ts->extra = 0;
142 getstr(ts)[l] = '\0'; /* ending 0 */
143 return ts;
144 }
以上是当字符串长度小于等于40时才这样，否则直接创建：
157 TString *luaS_createlngstrobj (lua_State *L, size_t l) {
158 TString *ts = createstrobj(L, l, LUA_TLNGSTR, LNGSTR_SEED);
159 ts->u.lnglen = l;
160 return ts;
161 }
从createstrobj中并没有看到为str分配空间并拷贝的地方，并且TString结构中无明显的空间，如注释所说“string bytes follow the end of this structure”，这里的实现如弹性数组"struct dummy {size_t len; char value[0];};"这种。
其他的实现诸如：
205 /*
206 ** create a new collectable object (with given type and size) and link
207 ** it to 'allgc' list.
208 */
209 GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
210 global_State *g = G(L);
211 GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
212 o->marked = luaC_white(g);
213 o->tt = tt;
214 o->next = g->allgc;
215 g->allgc = o;
216 return o;
217 }
324 /*
325 ** Get the actual string (array of bytes) from a 'TString'.
326 ** (Access to 'extra' ensures that value is really a 'TString'.)
327 */
328 #define getstr(ts) \
329 check_exp(sizeof((ts)->extra), cast(char *, (ts)) + sizeof(UTString))
194 void luaC_fix (lua_State *L, GCObject *o) {
195 global_State *g = G(L);
196 if (g->allgc != o)
197 return; /* if object is not 1st in 'allgc' list, it is in global short string table */
198 white2gray(o); /* they will be gray forever */
199 g->allgc = o->next; /* remove object from 'allgc' list */
200 o->next = g->fixedgc; /* link it to 'fixedgc' list */
201 g->fixedgc = o;
202 }
这里涉及的知识较多，没细分。比如垃圾回收相关的。
总结下，虽然lua中的string使用相对于其他语言来说，更方便，更可控，不需要考虑资源的泄露这些，但如果不了解这些实现，可能用的不够好。之前项目线上出现一个事故，就是因为使用第三方库时，因为提供给这边的接口是const修饰，表示不会修改外部参数，所以我当时在优化的时候，直接把中间的拷贝串给删除。然后直接把lua层的const char* 传递到那边接口，而那边接口居然改了我传的指针内容，导致整个进程，即多个luavm中的该字符都被替换成***，当然接口是否规范是另一回事。
所以个人感觉，还是更偏向于C/C++的使用，当然还是要看自己对这块的认知和熟悉程序，当然在项目中，对于语言工具的使用按照项目来。有些同学只停留在会用，并不会去了解一些实现甚至如何更好的使用，可能成长或许会少一些吧，猜测？
后续再简单分析下lua中的table实现，如何高效使用，以上的这两个结构对lua的回收也是有一定的影响，lua中其他的东西以后有时间再慢慢分析吧，我也是刚有点时间看看，可能有些不对的地方，欢迎指出来讨论。
