From 2fa5f652572c4f45c2c60ea97d79f01851f8d548 Mon Sep 17 00:00:00 2001
From: Markus Armbruster <armbru@pond.sub.org>
Date: Thu, 31 Dec 2009 13:14:36 +0100
Subject: [PATCH] Generation numbers to catch write back of stale copies

Oops when a stale copy is written back, i.e. the processor was yielded
since the copy was made.  Such bugs are difficult to spot.  Sequence
numbers catch them when they do actual harm (they also catch different
bugs).  Generation numbers catch them even when they don't.

New ef_generation to count generations.  Call new ef_make_stale() to
increment it whenever the processor may be yielded.

New struct emptypedstr member generation.  To conserve space, make it
a bit-field of twelve bits, i.e. generations are only recorded modulo
2^12.  Make sure all members of unit empobj_storage share it.  It is
only used in copies; its value on disk and in the cache is
meaningless.  Copies with generation other than ef_generation are
stale.  Stale copies that are a multiple of 2^12 generations old can't
be detected, but that is sufficiently improbable.

Set generation to ef_generation by calling new ef_mark_fresh() when
making copies in ef_read() and ef_blank().  nav_ship() and
fltp_to_list() make copies without going through ef_read(), and
therefore need to call ef_mark_fresh() as well.  Also call it in
obj_changed() to make check_sect_ok() & friends freshen their argument
when it is unchanged.

New must_be_fresh() oopses when its argument is stale.  Call it in
ef_write() to catch write back of stale copies.
---
 include/commodity.h          |  1 +
 include/empobj.h             |  1 +
 include/file.h               |  3 +++
 include/game.h               |  1 +
 include/land.h               |  1 +
 include/loan.h               |  1 +
 include/lost.h               |  1 +
 include/nat.h                |  2 ++
 include/nuke.h               |  1 +
 include/plane.h              |  1 +
 include/sect.h               |  1 +
 include/ship.h               |  1 +
 include/trade.h              |  1 +
 include/treaty.h             |  1 +
 src/lib/common/file.c        | 40 ++++++++++++++++++++++++++++++++++--
 src/lib/empthread/io.c       |  4 ++++
 src/lib/empthread/lwp.c      |  9 ++++++++
 src/lib/empthread/ntthread.c |  9 ++++++++
 src/lib/empthread/pthread.c  |  9 ++++++++
 src/lib/subs/check.c         |  6 +++++-
 src/lib/update/nav_ship.c    |  1 +
 src/lib/update/sail.c        |  1 +
 22 files changed, 93 insertions(+), 3 deletions(-)

diff --git a/include/commodity.h b/include/commodity.h
index 1f03fa78e..c6b628b3d 100644
--- a/include/commodity.h
+++ b/include/commodity.h
@@ -44,6 +44,7 @@ struct comstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned com_seqno: 12;
+    unsigned com_generation: 12;
     int com_uid;
     time_t com_timestamp;
     natid com_owner;
diff --git a/include/empobj.h b/include/empobj.h
index 9574073d0..183021eb5 100644
--- a/include/empobj.h
+++ b/include/empobj.h
@@ -57,6 +57,7 @@ struct empobj {
      */
     signed ef_type: 8;
     unsigned seqno: 12;
+    unsigned generation: 12;
     int uid;
     time_t timestamp;
     /* end of part matching struct emptypedstr */
diff --git a/include/file.h b/include/file.h
index 4c0424b42..58146d31c 100644
--- a/include/file.h
+++ b/include/file.h
@@ -87,6 +87,7 @@ struct empfile {
 struct emptypedstr {
     signed ef_type: 8;
     unsigned seqno: 12;
+    unsigned generation: 12;
     int uid;
     time_t timestamp;
 };
@@ -203,6 +204,8 @@ enum {
 
 extern struct castr *ef_cadef(int);
 extern int ef_read(int, int, void *);
+extern void ef_make_stale(void);
+extern void ef_mark_fresh(int, void *);
 extern void *ef_ptr(int, int);
 extern char *ef_nameof(int);
 extern time_t ef_mtime(int);
diff --git a/include/game.h b/include/game.h
index a58d1bdb8..109920d21 100644
--- a/include/game.h
+++ b/include/game.h
@@ -40,6 +40,7 @@ struct gamestr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned game_seqno: 12;
+    unsigned game_generation: 12;
     int game_uid;
     time_t game_timestamp;
     /* end of part matching struct empobj */
diff --git a/include/land.h b/include/land.h
index 5b1fb7079..d3c174a04 100644
--- a/include/land.h
+++ b/include/land.h
@@ -51,6 +51,7 @@ struct lndstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned lnd_seqno: 12;
+    unsigned lnd_generation: 12;
     int lnd_uid;		/* unit id (land #) */
     time_t lnd_timestamp;	/* Last time this unit was touched */
     natid lnd_own;		/* owner's country num */
diff --git a/include/loan.h b/include/loan.h
index d4fae4c70..713d88c23 100644
--- a/include/loan.h
+++ b/include/loan.h
@@ -44,6 +44,7 @@ struct lonstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned l_seqno: 12;
+    unsigned l_generation: 12;
     int l_uid;
     time_t l_timestamp;
     /* end of part matching struct empobj */
diff --git a/include/lost.h b/include/lost.h
index 0e40470c3..9fa7ab132 100644
--- a/include/lost.h
+++ b/include/lost.h
@@ -41,6 +41,7 @@ struct loststr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned lost_seqno: 12;
+    unsigned lost_generation: 12;
     int lost_uid;
     time_t lost_timestamp;	/* When it was lost */
     natid lost_owner;		/* Who lost it */
diff --git a/include/nat.h b/include/nat.h
index 5b658bdbb..d64f8036c 100644
--- a/include/nat.h
+++ b/include/nat.h
@@ -72,6 +72,7 @@ struct realmstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned r_seqno: 12;
+    unsigned r_generation: 12;
     int r_uid;			/* realm table index */
     time_t r_timestamp;		/* Last time this realm was touched */
     natid r_cnum;		/* country number */
@@ -85,6 +86,7 @@ struct natstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned nat_seqno: 12;
+    unsigned nat_generation: 12;
     int nat_uid;		/* equals nat_cnum */
     time_t nat_timestamp;
     natid nat_cnum;		/* our country number */
diff --git a/include/nuke.h b/include/nuke.h
index 6a0db83ff..ec697c711 100644
--- a/include/nuke.h
+++ b/include/nuke.h
@@ -44,6 +44,7 @@ struct nukstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned nuk_seqno: 12;
+    unsigned nuk_generation: 12;
     int nuk_uid;		/* unit id (nuke #) */
     time_t nuk_timestamp;	/* Last time this nuke was touched */
     natid nuk_own;
diff --git a/include/plane.h b/include/plane.h
index e77ee93ac..e080099b6 100644
--- a/include/plane.h
+++ b/include/plane.h
@@ -48,6 +48,7 @@ struct plnstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned pln_seqno: 12;
+    unsigned pln_generation: 12;
     int pln_uid;		/* unit id (plane #) */
     time_t pln_timestamp;	/* Last time this plane was touched */
     natid pln_own;		/* owning country */
diff --git a/include/sect.h b/include/sect.h
index 9b6fe8d8e..62e634cea 100644
--- a/include/sect.h
+++ b/include/sect.h
@@ -46,6 +46,7 @@ struct sctstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned sct_seqno: 12;
+    unsigned sct_generation: 12;
     int sct_uid;		/* equals XYOFFSET(sct_x, sct_y) */
     time_t sct_timestamp;	/* Last time this sector was written to */
     natid sct_own;		/* owner's country num */
diff --git a/include/ship.h b/include/ship.h
index 23cefa1f7..c4425b80a 100644
--- a/include/ship.h
+++ b/include/ship.h
@@ -65,6 +65,7 @@ struct shpstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned shp_seqno: 12;
+    unsigned shp_generation: 12;
     int shp_uid;		/* unit it (ship #) */
     time_t shp_timestamp;	/* Last time this ship was touched. */
     natid shp_own;		/* owner's country num */
diff --git a/include/trade.h b/include/trade.h
index 72ebdbbb9..41889265c 100644
--- a/include/trade.h
+++ b/include/trade.h
@@ -44,6 +44,7 @@ struct trdstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned trd_seqno: 12;
+    unsigned trd_generation: 12;
     int trd_uid;
     time_t trd_timestamp;
     natid trd_owner;
diff --git a/include/treaty.h b/include/treaty.h
index 440d7f533..f1c4cbb0a 100644
--- a/include/treaty.h
+++ b/include/treaty.h
@@ -41,6 +41,7 @@ struct trtstr {
     /* initial part must match struct empobj */
     signed ef_type: 8;
     unsigned trt_seqno: 12;
+    unsigned trt_generation: 12;
     int trt_uid;
     time_t trt_timestamp;
     /* end of part matching struct empobj */
diff --git a/src/lib/common/file.c b/src/lib/common/file.c
index f32bafa4b..b59e1ab52 100644
--- a/src/lib/common/file.c
+++ b/src/lib/common/file.c
@@ -57,9 +57,12 @@ static int do_read(struct empfile *, void *, int, int);
 static int do_write(struct empfile *, void *, int, int);
 static unsigned get_seqno(struct empfile *, int);
 static void new_seqno(struct empfile *, void *);
+static void must_be_fresh(struct empfile *, void *);
 static void do_blank(struct empfile *, void *, int, int);
 static int ef_check(int);
 
+static unsigned ef_generation;
+
 /*
  * Open the file-backed table TYPE (EF_SECTOR, ...).
  * HOW are flags to control operation.  Naturally, immutable flags are
@@ -360,6 +363,7 @@ ef_read(int type, int id, void *into)
 	cachep = ep->cache + (id - ep->baseid) * ep->size;
     }
     memcpy(into, cachep, ep->size);
+    ef_mark_fresh(type, into);
 
     if (ep->postread)
 	ep->postread(id, into);
@@ -522,9 +526,11 @@ ef_write(int type, int id, void *from)
 	if (ep->onresize && ep->onresize(type) < 0)
 	    return 0;
     }
-    if (id >= ep->baseid && id < ep->baseid + ep->cids)
+    if (id >= ep->baseid && id < ep->baseid + ep->cids) {
 	cachep = ep->cache + (id - ep->baseid) * ep->size;
-    else
+	if (cachep != from)
+	    must_be_fresh(ep, from);
+    } else
 	cachep = NULL;
     if (ep->prewrite)
 	ep->prewrite(id, cachep, from);
@@ -607,6 +613,35 @@ new_seqno(struct empfile *ep, void *buf)
     elt->seqno = old_seqno + 1;
 }
 
+void
+ef_make_stale(void)
+{
+    ef_generation++;
+}
+
+void
+ef_mark_fresh(int type, void *buf)
+{
+    struct empfile *ep;
+
+    if (ef_check(type) < 0)
+	return;
+    ep = &empfile[type];
+    if (!(ep->flags & EFF_TYPED))
+	return;
+    ((struct emptypedstr *)buf)->generation = ef_generation;
+}
+
+static void
+must_be_fresh(struct empfile *ep, void *buf)
+{
+    struct emptypedstr *elt = buf;
+
+    if (!(ep->flags & EFF_TYPED))
+	return;
+    CANT_HAPPEN(elt->generation != (ef_generation & 0xfff));
+}
+
 /*
  * Extend table TYPE by COUNT elements.
  * Any pointers obtained from ef_ptr() become invalid.
@@ -684,6 +719,7 @@ ef_blank(int type, int id, void *buf)
 	elt = buf;
 	elt->seqno = get_seqno(ep, elt->uid);
     }
+    ef_mark_fresh(type, buf);
 }
 
 /*
diff --git a/src/lib/empthread/io.c b/src/lib/empthread/io.c
index 6679dfc66..8016044d3 100644
--- a/src/lib/empthread/io.c
+++ b/src/lib/empthread/io.c
@@ -51,6 +51,7 @@
 #include <unistd.h>
 #include "empio.h"
 #include "empthread.h"
+#include "file.h"
 #include "ioqueue.h"
 #include "misc.h"
 #include "queue.h"
@@ -196,6 +197,9 @@ io_output(struct iop *iop, int wait)
     struct iovec iov[16];
     int n, res, cc;
 
+    if (wait)
+	ef_make_stale();
+
     if (!ioq_qsize(iop->output))
 	return 0;
 
diff --git a/src/lib/empthread/lwp.c b/src/lib/empthread/lwp.c
index 5889c5f12..d13737121 100644
--- a/src/lib/empthread/lwp.c
+++ b/src/lib/empthread/lwp.c
@@ -37,6 +37,7 @@
 #include <signal.h>
 #include <time.h>
 #include "empthread.h"
+#include "file.h"
 #include "misc.h"
 
 /* Flags that were passed to empth_init() */
@@ -65,6 +66,7 @@ empth_create(void (*entry)(void *), int size, int flags,
 {
     if (!flags)
 	flags = empth_flags;
+    ef_make_stale();
     return lwpCreate(1, entry, size, flags, name, 0, NULL, ud);
 }
 
@@ -89,18 +91,21 @@ empth_set_name(empth_t *thread, char *name)
 void
 empth_exit(void)
 {
+    ef_make_stale();
     lwpExit();
 }
 
 void
 empth_yield(void)
 {
+    ef_make_stale();
     lwpYield();
 }
 
 int
 empth_select(int fd, int flags, struct timeval *timeout)
 {
+    ef_make_stale();
     return lwpSleepFd(fd, flags, timeout);
 }
 
@@ -113,6 +118,7 @@ empth_wakeup(empth_t *a)
 int
 empth_sleep(time_t until)
 {
+    ef_make_stale();
     return lwpSleepUntil(until);
 }
 
@@ -123,6 +129,7 @@ empth_wait_for_signal(void)
     int sig, err;
     time_t now;
 
+    ef_make_stale();
     sigemptyset(&set);
     sigaddset(&set, SIGHUP);
     sigaddset(&set, SIGINT);
@@ -153,12 +160,14 @@ empth_rwlock_destroy(empth_rwlock_t *rwlock)
 void
 empth_rwlock_wrlock(empth_rwlock_t *rwlock)
 {
+    ef_make_stale();
     lwp_rwlock_wrlock(rwlock);
 }
 
 void
 empth_rwlock_rdlock(empth_rwlock_t *rwlock)
 {
+    ef_make_stale();
     lwp_rwlock_rdlock(rwlock);
 }
 
diff --git a/src/lib/empthread/ntthread.c b/src/lib/empthread/ntthread.c
index 579672204..67ae3ef49 100644
--- a/src/lib/empthread/ntthread.c
+++ b/src/lib/empthread/ntthread.c
@@ -56,6 +56,7 @@
 #include <process.h>
 #include "misc.h"
 #include "empthread.h"
+#include "file.h"
 #include "prototypes.h"
 #include "server.h"
 #include "sys/socket.h"
@@ -423,6 +424,7 @@ empth_create(void (*entry)(void *), int size, int flags,
     empth_t *pThread = NULL;
 
     loc_debug("creating new thread %s", name);
+    ef_make_stale();
 
     pThread = malloc(sizeof(*pThread));
     if (!pThread) {
@@ -501,6 +503,7 @@ empth_exit(void)
     empth_t *pThread = TlsGetValue(dwTLSIndex);
 
     loc_debug("empth_exit");
+    ef_make_stale();
     loc_BlockThisThread();
 
     TlsSetValue(dwTLSIndex, NULL);
@@ -516,6 +519,7 @@ empth_exit(void)
 void
 empth_yield(void)
 {
+    ef_make_stale();
     loc_BlockThisThread();
     Sleep(0);
     loc_RunThisThread(NULL);
@@ -541,6 +545,7 @@ empth_select(int fd, int flags, struct timeval *timeout)
 
     loc_debug("%s select on %d",
 	      flags == EMPTH_FD_READ ? "read" : "write", fd);
+    ef_make_stale();
     loc_BlockThisThread();
 
     hEventObject[0] = WSACreateEvent();
@@ -615,6 +620,7 @@ empth_sleep(time_t until)
     empth_t *pThread = TlsGetValue(dwTLSIndex);
     DWORD result;
 
+    ef_make_stale();
     loc_BlockThisThread();
 
     do {
@@ -645,6 +651,7 @@ empth_request_shutdown(void)
 int
 empth_wait_for_signal(void)
 {
+    ef_make_stale();
     loc_BlockThisThread();
     loc_RunThisThread(hShutdownEvent);
     return SIGTERM;
@@ -696,6 +703,7 @@ empth_rwlock_destroy(empth_rwlock_t *rwlock)
 void
 empth_rwlock_wrlock(empth_rwlock_t *rwlock)
 {
+    ef_make_stale();
     /* block any new readers */
     ResetEvent(rwlock->can_read);
     rwlock->nwrite++;
@@ -707,6 +715,7 @@ empth_rwlock_wrlock(empth_rwlock_t *rwlock)
 void
 empth_rwlock_rdlock(empth_rwlock_t *rwlock)
 {
+    ef_make_stale();
     loc_BlockThisThread();
     loc_RunThisThread(rwlock->can_read);
     ResetEvent(rwlock->can_write);
diff --git a/src/lib/empthread/pthread.c b/src/lib/empthread/pthread.c
index 3378b50bc..32293aecb 100644
--- a/src/lib/empthread/pthread.c
+++ b/src/lib/empthread/pthread.c
@@ -51,6 +51,7 @@
 #include <unistd.h>
 #include "misc.h"
 #include "empthread.h"
+#include "file.h"
 #include "prototypes.h"
 
 struct empth_t {
@@ -187,6 +188,7 @@ empth_create(void (*entry)(void *), int size, int flags,
     int eno;
 
     empth_status("creating new thread %s", name);
+    ef_make_stale();
 
     ctx = malloc(sizeof(empth_t));
     if (!ctx) {
@@ -262,6 +264,7 @@ empth_exit(void)
     empth_t *ctx = pthread_getspecific(ctx_key);
 
     empth_status("empth_exit");
+    ef_make_stale();
     pthread_mutex_unlock(&mtx_ctxsw);
     free(ctx->name);
     free(ctx);
@@ -271,6 +274,7 @@ empth_exit(void)
 void
 empth_yield(void)
 {
+    ef_make_stale();
     pthread_mutex_unlock(&mtx_ctxsw);
     pthread_mutex_lock(&mtx_ctxsw);
     empth_restorectx();
@@ -286,6 +290,7 @@ empth_select(int fd, int flags, struct timeval *timeout)
     empth_t *ctx;
     int res = 0;
 
+    ef_make_stale();
     pthread_mutex_unlock(&mtx_ctxsw);
     empth_status("select on %d for %d", fd, flags);
 
@@ -353,6 +358,7 @@ empth_sleep(time_t until)
     struct timeval tv;
     int res;
 
+    ef_make_stale();
     pthread_mutex_unlock(&mtx_ctxsw);
     do {
 	now = time(NULL);
@@ -373,6 +379,7 @@ empth_wait_for_signal(void)
     sigset_t set;
     int sig, err;
 
+    ef_make_stale();
     sigemptyset(&set);
     sigaddset(&set, SIGHUP);
     sigaddset(&set, SIGINT);
@@ -426,6 +433,7 @@ empth_rwlock_wrlock(empth_rwlock_t *rwlock)
 {
     empth_status("wrlock %s %d %d",
 		 rwlock->name, rwlock->nread, rwlock->nwrite);
+    ef_make_stale();
     rwlock->nwrite++;
     while (rwlock->nread != 0 || rwlock->nwrite != 1) {
 	empth_status("waiting for wrlock %s", rwlock->name);
@@ -441,6 +449,7 @@ empth_rwlock_rdlock(empth_rwlock_t *rwlock)
 {
     empth_status("rdlock %s %d %d",
 		 rwlock->name, rwlock->nread, rwlock->nwrite);
+    ef_make_stale();
     while (rwlock->nwrite) {
 	empth_status("waiting for rdlock %s", rwlock->name);
 	pthread_cond_wait(&rwlock->can_read, &mtx_ctxsw);
diff --git a/src/lib/subs/check.c b/src/lib/subs/check.c
index 77f91b72d..360ce913a 100644
--- a/src/lib/subs/check.c
+++ b/src/lib/subs/check.c
@@ -53,7 +53,11 @@ obj_changed(struct empobj *obj, size_t sz)
     get_empobj(obj->ef_type, obj->uid, &old);
     memcpy(&tobj, obj, sz);
     old.gen.timestamp = tobj.gen.timestamp = 0;
-    return memcmp(&tobj, &old, sz);
+    old.gen.generation = tobj.gen.generation = 0;
+    if (memcmp(&tobj, &old, sz))
+	return 1;
+    ef_mark_fresh(obj->ef_type, obj);
+    return 0;
 }
 
 int
diff --git a/src/lib/update/nav_ship.c b/src/lib/update/nav_ship.c
index 32c01c08f..0a0206988 100644
--- a/src/lib/update/nav_ship.c
+++ b/src/lib/update/nav_ship.c
@@ -268,6 +268,7 @@ nav_ship(struct shpstr *sp)
     mlp = malloc(sizeof(struct ulist));
     mlp->chrp = (struct empobj_chr *)(mchr + sp->shp_type);
     mlp->unit.ship = *sp;
+    ef_mark_fresh(EF_SHIP, &mlp->unit.ship);
     mlp->mobil = sp->shp_mobil;
     emp_insque(&mlp->queue, &ship_list);
 
diff --git a/src/lib/update/sail.c b/src/lib/update/sail.c
index c10c211ea..a52408333 100644
--- a/src/lib/update/sail.c
+++ b/src/lib/update/sail.c
@@ -347,6 +347,7 @@ fltp_to_list(struct fltheadstr *fltp, struct emp_qelem *list)
 	sp = getshipp(fe->num);
 	mlp->chrp = (struct empobj_chr *)(mchr + sp->shp_type);
 	mlp->unit.ship = *sp;
+	ef_mark_fresh(EF_SHIP, &mlp->unit.ship);
 	mlp->mobil = fe->mobil;
 	emp_insque(&mlp->queue, list);
     }
-- 
2.43.0