rewrite core function of tumpserver, maintaining friend relation 300 timers faster.

git-svn-id: http://opensvn.csie.org/pttbbs/trunk/pttbbs@3286 63ad8ddf-47c3-0310-b6dd-a9e9d9715204

3 files changed, 607 insertions, 4 deletions

diff --git a/cacheserver/Makefile b/cacheserver/Makefile
index e09edcca..0df01e29 100644
--- a/cacheserver/Makefile
+++ b/cacheserver/Makefile
@@ -1,19 +1,24 @@
 # $Id$
 .include "../pttbbs.mk"
 
-PROGRAMS=	utmpserver utmpsync
+PROGRAMS=	utmpserver utmpsync utmpserver2
 UTILOBJ=	../util/util_stuff.o ../util/util_var.o ../util/util_file.o ../util/util_cache.o ../util/util_passwd.o ../util/util_record.o
 
 all:	${PROGRAMS}
 
-.SUFFIXES: .c .o
-.c.o:	
+.SUFFIXES: .c .cpp .o
+.c.o:
 	$(CCACHE) $(CC) $(CFLAGS) -c $*.c
+.cpp.o:
+	$(CCACHE) $(CXX) $(CFLAGS) -c $*.cpp
 
 utmpserver: utmpserver.o $(UTILOBJ)
 	${CC} ${CFLAGS} ${LDFLAGS} -o $* $*.o $(UTILOBJ)
+utmpserver2: utmpserver2.o friend.o $(UTILOBJ)
+	${CXX} ${CFLAGS} ${LDFLAGS} -o $* $*.o $(UTILOBJ) friend.o
 utmpsync: utmpsync.o $(UTILOBJ)
 	${CC} ${CFLAGS} ${LDFLAGS} -o $* $*.o $(UTILOBJ)
 
+
 clean:
-	rm -f *~ ${PROGRAMS}
+	rm -f *~ ${PROGRAMS} friend.o utmpserver.o utmpserver2.o utmpsync.o
diff --git a/cacheserver/friend.cpp b/cacheserver/friend.cpp
new file mode 100644
index 00000000..4f8e9663
--- /dev/null
+++ b/cacheserver/friend.cpp
@@ -0,0 +1,352 @@
+#define NDEBUG
+#include <algorithm>
+#include <cassert>
+
+// for some constant and type
+#include "bbs.h"
+
+/* for each login of user, 
+ * input: my index, friend[MAX_FRIEND] of uid, reject[MAX_REJECT] of uid,
+ * for all my relation,
+ * output: his index, his uid, relation to me, relation to him
+ */
+/* 除了 user 及 utmp 之外, 全部的 ref index 都是雙向的, 確保 insert & delete O(1) */
+/* 當沒有人 refer 時則 resource recycle */
+
+typedef int Uid;
+typedef int Idx;
+
+
+struct Relation {
+    Uid him;
+    short him_offset;
+
+    Relation(Uid _him, short _him_offset=-1) :him(_him),him_offset(_him_offset) {}
+};
+
+template<class T>
+struct freelist {
+    static const int KEEP = 64;
+    static T* list[8][KEEP]; // 2^0~2^7
+    static int tail[8];
+
+#define IS_2xxN(a)      (a && (a&(a-1))==0)
+    static T* alloc(int n) {
+	assert(n>0);
+	if(n<256 && IS_2xxN(n) && sizeof(T)*n<65536) {
+	    int t=n;
+	    int slot;
+	    for(slot=0; t>1; t/=2)
+		slot++;
+	    assert(0<=slot && slot<8);
+	    if(tail[slot]) {
+		return list[slot][--tail[slot]];
+	    }
+	}
+	return (T*)malloc(sizeof(T)*n);
+    }
+    static void free(T* p, int n) {
+	assert(n>0);
+	if(n<256 && IS_2xxN(n) && sizeof(T)*n<65536) {
+	    int t=n;
+	    int slot;
+	    for(slot=0; t>1; t/=2)
+		slot++;
+	    assert(0<=slot && slot<8);
+	    if(tail[slot]<KEEP) {
+		list[slot][tail[slot]++]=p;
+		return;
+	    }
+	}
+	::free(p);
+    }
+};
+
+template<class T> T*  freelist<T>::list[8][KEEP];
+template<class T> int freelist<T>::tail[8]={0};
+
+template<class T,int MIN_ROOM = 8, class S = int>
+struct myvector {
+    // 大致上想要 STL vector, 但 STL 的 capacity 只會增加不會縮小
+    // (後來發現, 以 online friend 來說, capacity 不會縮小其實沒什麼影響)
+    // 此外, pointer 在 64bit 機器上要 8bytes, basic overhead 8*3 bytes,
+    // 但我的資料量沒那麼大, 改用 S(int or short) 存 size & capacity 比較省
+    T *base;
+    S room, n;
+
+    myvector() :base(0),room(0),n(0) {}
+    ~myvector() {
+	clear();
+    }
+    S append(T data) {
+	if(room<n+1)
+	    resizefor(n+1);
+	base[n++]=data;
+	return n-1;
+    }
+    void pop_back() {
+	assert(n>0);
+	n--;
+	resizefor(n);
+    }
+    void clear() {
+	n=0;
+	resizefor(n);
+    }
+    /*
+    T& operator[](int idx) {
+	return base[idx];
+    }
+    */
+
+    void resizefor(S size) {
+	assert(size>=n);
+	if(size==0) {
+	    if(base) freelist<T>::free(base, room);
+	    base=0;
+	    room=0;
+	} else {
+	    S origroom=room;
+	    if(room==0)
+		room=MIN_ROOM;
+	    while(room<size) room=S(room*2);
+	    if(size<MIN_ROOM) size=MIN_ROOM;
+	    while(room/2>size) room=S(room/2);
+	    if(room!=origroom || base==0) {
+		//base=(T*)realloc(base, sizeof(T)*room);
+		T* tmp=freelist<T>::alloc(room);
+		assert(tmp);
+		if(n>0)
+		    memcpy(tmp, base, sizeof(T)*n);
+		if(base!=0)
+		    freelist<T>::free(base, origroom);
+		base=tmp;
+	    }
+	    assert(base);
+	}
+    }
+};
+
+template<class R,class B>
+struct RelationList: public myvector<Relation, 8, short> {
+    RelationList() :myvector<Relation, 8, short>() {}
+    void add(Uid me, Uid him) {
+	assert(me!=him);
+	RelationList<B,R>& bl=R::backlist(him);
+	short me_offset=append(Relation(him));
+       	short him_offset=bl.append(Relation(me,me_offset));
+
+	setbackoffset(me_offset,him_offset);
+	assert(bl.base[him_offset].him==me);
+	assert(bl.base[him_offset].him_offset==me_offset);
+    }
+    void deleteall(Uid me) {
+	for(int i=0; i<n; i++) {
+	    RelationList<B,R>& bl=R::backlist(base[i].him);
+	    assert(bl.base[base[i].him_offset].him==me);
+	    assert(bl.base[base[i].him_offset].him_offset==i);
+	    bl.delete_half(base[i].him_offset);
+	    //try_recycle(base[i].him); // dirty
+	}
+	clear();
+    }
+    public:
+    void setbackoffset(short which,short offset) {
+	assert(0<=which && which<n);
+	base[which].him_offset=offset;
+    }
+    void delete_half(short offset) {
+	assert(0<=offset && offset<n);
+	if(offset<n-1) {
+	    base[offset]=base[n-1];
+	    R::backlist(base[offset].him).setbackoffset(base[offset].him_offset,offset);
+	}
+	pop_back();
+    }
+    friend void RelationList<B,R>::add(Uid me, Uid him);
+    friend void RelationList<B,R>::deleteall(Uid me);
+    friend void RelationList<B,R>::delete_half(short offset);
+};
+
+struct Like;
+struct Likeby;
+struct Hate;
+struct Hateby;
+struct Like: public Relation {
+    Like(Uid _him, short _him_offset=-1) :Relation(_him,_him_offset) {}
+    static RelationList<Likeby,Like>& backlist(Uid him);
+};
+struct Likeby: public Relation {
+    Likeby(Uid _him, short _him_offset=-1) :Relation(_him,_him_offset) {}
+    static RelationList<Like,Likeby>& backlist(Uid him);
+};
+struct Hate: public Relation {
+    Hate(Uid _him, short _him_offset=-1) :Relation(_him,_him_offset) {}
+    static RelationList<Hateby,Hate>& backlist(Uid him);
+};
+struct Hateby: public Relation {
+    Hateby(Uid _him, short _him_offset=-1) :Relation(_him,_him_offset) {}
+    static RelationList<Hate,Hateby>& backlist(Uid him);
+};
+
+
+struct Utmp {
+    Utmp() {
+	for(int i=0; i<USHM_SIZE; i++)
+	    utmp[i]=-1;
+    }
+    /*
+    Uid& operator[](int idx) {
+	return utmp[idx];
+    }
+    */
+    public:
+    Uid utmp[USHM_SIZE];
+};
+Utmp utmp;
+
+struct BBSUser {
+    Uid me;
+    int online;
+    /* assume utmplist is short, so just use plain vector and linear search */
+    myvector<int,2> utmplist;
+
+    RelationList<Like,Likeby> like;
+    RelationList<Hate,Hateby> hate;
+    RelationList<Likeby,Like> likeby;
+    RelationList<Hateby,Hate> hateby;
+
+    BBSUser() :me(-1),online(0),utmplist(),like(),hate(),likeby(),hateby() {}
+    BBSUser(Uid uid) :me(uid),online(0),utmplist(),like(),hate(),likeby(),hateby() {}
+
+    void login(int utmpidx, const Uid likehim[MAX_FRIEND], const Uid hatehim[MAX_REJECT]) {
+	if(online>0) {
+	    /* multiple login 的話, 以最後一次的 like/hate 為準 */
+	    like.deleteall(me);
+	    hate.deleteall(me);
+	}
+	utmp.utmp[utmpidx]=me;
+	utmplist.append(utmpidx);
+	online++;
+	assert(online==utmplist.n);
+	for(int i=0; i<MAX_FRIEND && likehim[i]; i++)
+	    if(likehim[i]!=me)
+		like.add(me, likehim[i]);
+	for(int i=0; i<MAX_REJECT && hatehim[i]; i++)
+	    if(hatehim[i]!=me)
+		hate.add(me, hatehim[i]);
+    }
+
+    void logout(int utmpidx) {
+	assert(utmp.utmp[utmpidx]==me);
+	assert(online==utmplist.n);
+	for(int i=0; i<utmplist.n; i++)
+	    if(utmplist.base[i]==utmpidx) {
+		utmplist.base[i]=utmplist.base[utmplist.n-1];
+		utmplist.pop_back();
+		break;
+	    }
+	utmp.utmp[utmpidx]=-1;
+	online--;
+	assert(online==utmplist.n);
+	like.deleteall(me);
+	hate.deleteall(me);
+    }
+    bool isfree() const {
+	return online==0 && like.n==0 && hate.n==0 && likeby.n==0 && hateby.n==0;
+    }
+};
+
+struct UserList {
+    BBSUser users[MAX_USERS];
+
+    UserList() {
+	for(int i=0; i<MAX_USERS; i++)
+	    users[i].me=i;
+    }
+    void login(Uid uid, Idx idx, const Uid likehim[MAX_FRIEND], const Uid hatehim[MAX_REJECT]) {
+	assert(uid<MAX_USERS);
+	assert(idx<USHM_SIZE);
+	/* 由於不會收到 logout event, 因此 logout 只發生在 utmp override */
+	if(utmp.utmp[idx]!=-1) users[utmp.utmp[idx]].logout(idx);
+	users[uid].login(idx, likehim, hatehim);
+    }
+};
+
+struct UserList userlist;
+RelationList<Likeby,Like>& Like::backlist(Uid him) { return userlist.users[him].likeby; }
+RelationList<Like,Likeby>& Likeby::backlist(Uid him) { return userlist.users[him].like; }
+RelationList<Hateby,Hate>& Hate::backlist(Uid him) { return userlist.users[him].hateby; }
+RelationList<Hate,Hateby>& Hateby::backlist(Uid him) { return userlist.users[him].hate; }
+
+struct Result {
+    Uid who;
+    int bits;
+    Result(Uid _who, int _bits) :who(_who),bits(_bits) {}
+    bool operator<(const Result& b) const {
+	return who<b.who;
+    }
+};
+
+int reverse_friend_stat(int stat)
+{
+    int             stat1 = 0;
+    if (stat & IFH) stat1 |= HFM;
+    if (stat & IRH) stat1 |= HRM;
+    if (stat & HFM) stat1 |= IFH;
+    if (stat & HRM) stat1 |= IRH;
+    return stat1;
+}
+
+extern "C" void utmplogin(int uid, int index, const int like[MAX_FRIEND], const int hate[MAX_REJECT])
+{
+    /* login */
+    userlist.login(uid, index, like, hate);
+}
+
+extern "C" int genfriendlist(int uid, int index, ocfs_t *fs, int maxfs)
+{
+    /* collect data */
+    BBSUser& u=userlist.users[uid];
+    myvector<Result,64,short> work;
+    for(int i=0; i<u.like.n; i++) work.append(Result(u.like.base[i].him, IFH));
+    for(int i=0; i<u.hate.n; i++) work.append(Result(u.hate.base[i].him, IRH));
+    for(int i=0; i<u.likeby.n; i++) work.append(Result(u.likeby.base[i].him, HFM));
+    for(int i=0; i<u.hateby.n; i++) work.append(Result(u.hateby.base[i].him, HRM));
+
+    /* sort */
+    std::sort(work.base, work.base+work.n);
+    /* merge */
+    if(work.n>0) {
+	int newn=1;
+	for(int i=1; i<work.n; i++)
+	    if(work.base[i].who==work.base[newn-1].who) {
+		work.base[newn-1].bits|=work.base[i].bits;
+	    } else {
+		work.base[newn++]=work.base[i];
+	    }
+	work.n=newn;
+    }
+    /* fill */
+    int nfs=0;
+    for(int i=0; i<work.n && nfs<maxfs; i++) {
+	BBSUser& h=userlist.users[work.base[i].who];
+	for(int j=0; j<h.utmplist.n && nfs<maxfs; j++) {
+	    int rstat=reverse_friend_stat(work.base[i].bits);
+	    fs[nfs].index=h.utmplist.base[j];
+	    fs[nfs].uid=h.me;
+	    fs[nfs].friendstat=(work.base[i].bits<<24)|h.utmplist.base[j];
+	    fs[nfs].rfriendstat=(rstat<<24)|index;
+	    nfs++;
+	}
+    }
+    return nfs;
+}
+
+extern "C" void utmplogoutall(void)
+{
+    for(int i=0; i<USHM_SIZE; i++)
+	if(utmp.utmp[i]!=-1)
+	    userlist.users[utmp.utmp[i]].logout(i);
+}
+
diff --git a/cacheserver/utmpserver2.c b/cacheserver/utmpserver2.c
new file mode 100644
index 00000000..d4e86f57
--- /dev/null
+++ b/cacheserver/utmpserver2.c
@@ -0,0 +1,246 @@
+#include <stdio.h>
+#include <sys/time.h>
+
+#include "bbs.h"
+
+extern void utmplogin(int uid, int index, const int like[MAX_FRIEND], const int hate[MAX_REJECT]);
+extern int genfriendlist(int uid, int index, ocfs_t *fs, int maxfs);
+extern void utmplogoutall(void);
+#ifdef FAKEDATA
+FILE *fp;
+#endif
+#ifdef UTMPLOG
+FILE *logfp;
+#endif
+
+
+#ifdef NOFLOODING
+#define MAXWAIT 1024
+#define FLUSHTIME (3600*6)
+
+struct {
+    time_t  lasttime;
+    int     count;
+} flooding[MAX_USERS];
+
+int nWaits, lastflushtime;
+struct {
+    int     uid;
+    int     fd;
+    int     index;
+} waitqueue[MAXWAIT];
+
+void flushwaitqueue(void)
+{
+    int     i;
+    for( i = 0 ; i < nWaits ; ++i ) {
+	processlogin(waitqueue[i].fd, waitqueue[i].uid, waitqueue[i].index);
+	close(waitqueue[i].fd);
+    }
+    lastflushtime = time(NULL);
+    nWaits = 0;
+    memset(flooding, 0, sizeof(flooding));
+}
+#endif /* NOFLOODING */
+
+void syncutmp(int cfd) {
+    int i;
+    int like[MAX_FRIEND];
+    int hate[MAX_REJECT];
+
+#ifdef UTMPLOG
+    int x=-1;
+    if(logfp && ftell(logfp)> 500*(1<<20)) {
+	fclose(logfp);
+	logfp=NULL;
+    }
+    if(logfp) fwrite(&x, sizeof(x), 1, logfp);
+#endif
+
+    printf("logout all\n");
+    utmplogoutall();
+    fprintf(stderr,"sync begin\n");
+    for(i=0; i<USHM_SIZE; i++) {
+	int uid;
+#ifdef FAKEDATA
+	fread(&uid, sizeof(uid), 1, fp);
+	if(uid==-2)
+	    break;
+	fread(like, sizeof(like), 1, fp);
+	fread(hate, sizeof(hate), 1, fp);
+#else
+	if( toread(cfd, &uid, sizeof(uid)) <= 0 ||
+		toread(cfd, like, sizeof(like)) <= 0 ||
+		toread(cfd, hate, sizeof(hate)) <= 0)
+	    break;
+#endif
+#ifdef UTMPLOG
+	if(logfp) {
+	    fwrite(&uid, sizeof(uid), 1, logfp);
+	    fwrite(like, sizeof(like), 1, logfp);
+	    fwrite(hate, sizeof(hate), 1, logfp);
+	}
+#endif
+
+	if(uid != 0)
+	    utmplogin(uid, i, like, hate);
+    }
+    if(i<USHM_SIZE) {
+#ifdef UTMPLOG
+	int x=-2;
+	if(logfp) fwrite(&x, sizeof(x), 1, logfp);
+#endif
+    }
+
+    fprintf(stderr,"sync end\n");
+}
+
+void processlogin(int cfd, int uid, int index)
+{
+    int like[MAX_FRIEND];
+    int hate[MAX_REJECT];
+    /* 因為 logout 的時候並不會通知 utmpserver , 可能會查到一些
+       已經 logout 的帳號。所以不能只取 MAX_FRIEND 而要多取一些 */
+#define MAX_FS   (2 * MAX_FRIEND)
+    int nfs;
+    ocfs_t fs[MAX_FS];
+
+#ifdef FAKEDATA
+    fread(like, sizeof(like), 1, fp);
+    fread(hate, sizeof(hate), 1, fp);
+#else
+    if(toread(cfd, like, sizeof(like)) <= 0 ||
+	    toread(cfd, hate, sizeof(hate)) <= 0)
+	return;
+#endif
+#ifdef UTMPLOG
+    if(logfp) {
+	int x=-3;
+	fwrite(&x, sizeof(x), 1, logfp);
+	fwrite(&uid, sizeof(uid), 1, logfp);
+	fwrite(&index, sizeof(index), 1, logfp);
+	fwrite(like, sizeof(like), 1, logfp);
+	fwrite(hate, sizeof(hate), 1, logfp);
+    }
+#endif
+
+    utmplogin(uid, index, like, hate);
+    nfs=genfriendlist(uid, index, fs, MAX_FS);
+#ifndef FAKEDATA
+    towrite(cfd, fs, sizeof(ocfs_t) * nfs);
+#endif
+}
+
+int main(int argc, char *argv[])
+{
+    struct  sockaddr_in     clientaddr;
+    int     ch, port = 5120, sfd, cfd, len;
+    char   *iface_ip = NULL;
+    int cmd;
+    int uid,index;
+    int fail;
+
+#ifdef UTMPLOG
+    logfp = fopen("utmp.log","a");
+    if(logfp && ftell(logfp)> 500*(1<<20)) {
+	fclose(logfp);
+	logfp=NULL;
+    }
+#endif
+
+    while( (ch = getopt(argc, argv, "p:i:h")) != -1 )
+	switch( ch ){
+	case 'p':
+	    port = atoi(optarg);
+	    break;
+	case 'i':
+	    iface_ip = optarg;
+	    break;
+	case 'h':
+	default:
+	    fprintf(stderr, "usage: utmpserver [-i interface_ip] [-p port]\n");
+	    return 1;
+	}
+
+#ifdef FAKEDATA
+    fp=fopen("utmp.data","rb");
+#else
+    if( (sfd = tobind(iface_ip, port)) < 0 )
+	return 1;
+#endif
+#ifdef NOFLOODING
+    lastflushtime = time(NULL);
+#endif
+    while(1) {
+#ifdef NOFLOODING
+	if( lastflushtime < (time(NULL) - 1800) )
+	    flushwaitqueue();
+#endif
+
+#ifdef FAKEDATA
+	if(fread(&cmd, sizeof(cmd), 1, fp)==0) break;
+#else
+	len = sizeof(clientaddr);
+	if( (cfd = accept(sfd, (struct sockaddr *)&clientaddr, &len)) < 0 ){
+	    if( errno != EINTR )
+		sleep(1);
+	    continue;
+	}
+	toread(cfd, &cmd, sizeof(cmd));
+#endif
+
+	if(cmd==-1) {
+	    syncutmp(cfd);
+#ifndef FAKEDATA
+	    close(cfd);
+#endif
+	    continue;
+	}
+
+	fail=0;
+#ifdef FAKEDATA
+	fread(&uid, sizeof(uid), 1, fp);
+	fread(&index, sizeof(index), 1, fp);
+#else
+	index=cmd; // bad protocol
+	if(toread(cfd, &uid, sizeof(uid)) <= 0)
+	    fail=1;
+#endif
+	if(index>=USHM_SIZE) {
+	    fprintf(stderr, "bad index=%d\n",index);
+	    fail=1;
+	}
+
+	if(fail) {
+#ifndef FAKEDATA
+	    close(cfd);
+#endif
+	    continue;
+	}
+
+#ifdef NOFLOODING
+	if( (time(NULL) - flooding[uid].lasttime) < 20 )
+	    ++flooding[uid].count;
+	if( flooding[uid].count > 10 ){
+	    if( nWaits == MAXWAIT )
+		flushwaitqueue();
+	    waitqueue[nWaits].uid = uid;
+	    waitqueue[nWaits].index = index;
+	    waitqueue[nWaits].fd = cfd;
+	    ++nWaits;
+
+	    continue;
+	}
+	flooding[uid].lasttime = time(NULL);
+#endif
+
+	processlogin(cfd, uid, index);
+#ifndef FAKEDATA
+	close(cfd);
+#endif
+    }
+#ifdef FAKEDATA
+    fclose(fp);
+#endif
+    return 0;
+}