如何恢复全局INDEX

一般来说,当需要分配全局惟一id时,一般都会有一个变量来记录当前最新的id值,比如叫INDEX变量。

每次需要分配id时,只要简单的自增一下INDEX变量,然后INDEX的值即为当前分配出去的ID的值。

为了最大可能的延迟复用已经分配过的id,一般来说不会去特殊处理INDEX变量,即每次自增INDEX,并允许回绕情况的发生。

但是最近碰到问题就是,我有一堆分配过的id,如何重新恢复出INDEX的值。具体场景如下:

struct obj {
        unsigned int id;
        time_t createtime;
        ...
}

每一个obj对象都需要有一个全局惟一id和创建时间(createtime字段)与其关联,因此每new一个obj对象就需要为其分配一个不重复的全局id。

obj可以被人为删除,也会被过期删除,因此无法保证在任何时间所有还存活着的obj对象id是连续的。这些obj对象会被定时写入数据库。

一旦进程被重启,程序会从数据库加载所有还存活着的obj对象,以便可以恢复现场,使重启进程这一操作透明。要保证整个逻辑正确性,还必须要能正确的恢复出INDEX变量。

那么问题来了,而由于某种原因,INDEX并不方便被存入数据库中。

因此必须要根据现有的存活obj对象来恢复出在进程重启前的INDEX的值。

第一反应,肯定是遍历一之后找到obj对象中最大的id即为原来的INDEX,但是这里有一个陷阱就是INDEX会回绕,一旦INDEX会回绕之后,这个算法就不正确了。

考虑这样一种情况,进程运行了数月都没有重启,这时残留的obj对象id可能就只剩下0xfffffffe,0xffffffff,0,1,3,5这些了,重启之后采用上述算法无法重新恢复出重启前INDEX的值为5.

再一看,还有一个createtime用作参考,只要取obj对象中createtime最大的那个对象的id为INDEX就行了。

然而,由于createtime是以秒为单位的,逻辑上无法保证1秒只创建一个obj对象,问题再次绕回到第一个算法所遇到的困境。

因此,看起来,想要正确恢复出INDEX的值就必须解决回绕的问题。

要解决这个问题,就必须要有一种大小比较算法,这种算法即使在回绕时,也能正确判断大小。比如在0xfffffffe,0xffffffff,0,1,3,5这一堆id中,此算法会认为5是最大值,而在3,5,7,9这一块id中认为9才是最大值。

那么究竟有没有这种算法呢?比较巧的是,还真有这种算法。

假设有A,B,C三个32位无符号值,C=(A+B) % 4G。那么只要B大于0且小于2G,C – A就一定大于0。不过这里有一个陷阱,如果A和C是无符号变量,那么一定要将C-A的值转换为int之后再使用。

再回到设定场景中去,虽然我们1秒可以new很多个obj对象,但是绝不可能new出2G个之多。

有了这个事实和算法,答案就呼之欲出了,其中一种实现如下:

unsigned int id = 0;
time_t time = 0;
for (auto const &obj:objs) {
        if (obj.createtime < time)
                continue;
        if (obj.createtime > time) {
                time = obj.createtime;
                id = obj.id;
        } else if ((int)(id - obj.id) < 0) {
                 id = obj.id
        }
}
//now we got the final INDEX value

ps. 在阐述这个blog之前,我曾请教了几个人,但似乎并没有其他更好的做法,觉得这个实现还算精巧,就做个笔记.

为什么要有头文件

我在写C文件时,一般会首先确定这个模块需要哪些功能,然后在头文件中定义相应的接口函数。之后才是在C文件中实现,在实现过程中除非有遗漏的接口,不然是不会再切回头文件的,一般辅助函数我都是直接以static的方式定义在C文件中。

在写C++代码时,这些代码辅助类的函数,都必需要以private的方式在头文件中声明。这会导致在写代码时,需要频繁在h/cpp之间切换,极度令人不舒服。

因此每次在写C++代码时,都免不了在心里抱怨几句为什么不把private函数直接定义在cpp文件中,或者干脆像java一样不要头文件算了。

前两天把这事跟朋友抱怨了一下,结果竟然得到了一个反问为什么需要头文件,头文件的作用到底是什么?

有人说头文件是为了展现接口,以头文件和.a或.so发布时,别人只要看头文件就可以知道提供了什么接口,然而对于java这类没有头文件的语言来讲只要一个工具同样可以提取出来class文件中的public接口信息。因此我觉得还是需要从编译器角度来分析一下头文件的用途。

那么C语言的头文件到底起到什么作用呢?且看下面一段代码(ps.为了使这段代码在任何平台上效果都一样,使用了stdint.h中的可移植类型):

////////////compile: gcc -o a a.c b.c
////////////b.h
#ifndef _B_H
#define _B_H
#include <stdint.h>
struct test {
        uint8_t a1;
        uint8_t a2;
        uint8_t b1;
        uint8_t b2;
};
#endif
////////////b1.h
#ifndef	_B1_H
#define	_B1_H
#include <stdint.h>
struct test {
        uint16_t a;
        uint16_t b;
};
extern struct test T;
#endif
////////////b.c
#include "b.h"
struct test T = {.a1 = 1, .a2 = 2, .b1 = 3, .b2 = 4};
////////////a.c
#include &lt;stdio.h&gt;
#include "b1.h"
int main()
{
        printf("a:0x%x b:0x%x\n", T.a, T.b);
        return 0;
}

这段代码的运行结果很有意思,是’a:0x201 b:0x403’。

这段代码编译器不会报任何错误,甚至连警告也不会报。为什么会这样呢?这要从几个.c文件变成elf(linux)/exe(win)文件过程说起。

从c文件到可执行文件至少要经过两个阶段,即‘编译’和‘链接’。
‘编译’会将相应的C代码转换成相应的汇编,但保留符号名(如上述代码中的T)然后生成.o文件.
而‘链接’会收集所有的.o文件然后为每个符号分配地址,并将.o文件中的相应的符号换成相关地址并生成相应格式的可执行文件(ps.上面的流程并不严谨).

以a.c中的代码为例,在编译时T.a语句其实就已经转换为了与*((uint16_t*)((uint8_t *)&T+0))等效的汇编代码,相应的T.b的语句等效*((uint16_t*)((uint8_t *)&T+sizeof(uint16_t))).这一点其实可以通过gcc -S来反汇编证明。

那么头文件的功能就呼之欲出了,在‘编译期间’为了保证能生成正确的汇编代码,必须要头文件指明struct的字段分布,及此c文件中引用的符号在外部有提供(这就是声明的意义)。

当然头文件所带来的问题也正像上述代码中描述的一样,当给出一个错误的头文件时编译器并不会察觉,在没有源码的情况下,这种错误极难发现。

那么java是如何实现的呢?我尝试着写了两个类编译了一下。猜测,他应该是在编译时自动提取出本类的声明信息,然后放在.class文件中,当javac编译时用到某个类时就去找当前目录下打开‘类.class’文件,从其中提出取类的声明信息,从而达到与有头文件有相同的效果。

ps. 我怀疑.class的声明信息与其反射机制有密切关系,但是jvm的代码量有20多万行,找到其反射部分的实现还是比较麻烦的,天气这么冷还是先放一下:)

pps. 如果C语言也这么搞的话,似乎是行不通的,java中的类的概念,可以约定使用哪个类就从‘类名.class’文件中寻找,如果是C呢,找一个struct test的布局去test.o中找?那找一个函数helloworld应该去哪个文件中找呢?


在与Qwerty交流后发现,查找helloworld函数时可以根据此c文件import的模块来实现,那么似乎为C引用import机制也并不是不太可能。

简单思考了一下,在不改变现有编译流程的情况下,似乎可以为c文件引入一个轻量级import机制来代替头文件。

我们可以在编译器(如:gcc)之上包个壳,假设叫xcc,然后为.o为文件也加上一个壳叫.m。

.m文件其实包含了其源文件中的public的函数接口定义和一个完整的gcc编译出来的.o文件内容。

xcc的执行流程大概如下:

1. 使用xcc编译A.c文件时,xcc首先分析出A.c文件中的声明信息’T’及import的模块’M’。
2. 从M.m文件中提取出M.c文件中的声明信息T,并生成M.h文件,之后将a.c中的import ‘M’替换为#include “M.h”,并另存为到/tmp/A.c.tmp。
3. 调用相应的编译器如’gcc’编译/tmp/A.c.tmp生成A.o
4. 将A.c的声明信息T追加到A.o的最后(之所以追加到最后,是因为A.m可以被当作A.o直接传给ld, 这样我们就不用为ld再包一个壳了)

有一个特例,一个struct是否要导出,必须要等分析完所有的导出接口之后才能决定,如果在导出接口参数中有用到,那么我们就可以将其导出到头文件中。

如此,我们就有了一个兼容import的C语言。