From dc9d847b8ba8bcf7da2ca7b47695abf51745f3eb Mon Sep 17 00:00:00 2001
From: Markus Armbruster <armbru@pond.sub.org>
Date: Fri, 21 Mar 2008 14:22:07 +0100
Subject: [PATCH] Add sequence numbers to game state (experimental)

This catches output dependency violations, e.g. two threads doing a
read-modify-write without synchronization.

New struct emptypedstr member seqno.  Make sure all members of unit
empobj_storage share it.  Set it in ef_blank() and ef_set_uid(), step
it in ef_write().  fairland and files don't use ef_set_uid(); need to
set it manually in files.c's main() and file_sct_init().

Factor do_read() out of fillcache() to make it available for
new get_seqno().
---
 include/commodity.h     |   1 +
 include/empobj.h        |   1 +
 include/file.h          |   2 +
 include/game.h          |   1 +
 include/land.h          |   1 +
 include/loan.h          |   1 +
 include/lost.h          |   1 +
 include/nat.h           |   2 +
 include/news.h          |   1 +
 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/commands/edit.c |   6 +--
 src/lib/commands/swap.c |   4 +-
 src/lib/common/file.c   | 110 +++++++++++++++++++++++++++++++++++-----
 src/lib/subs/nreport.c  |   2 +-
 src/util/files.c        |   3 ++
 20 files changed, 124 insertions(+), 18 deletions(-)

diff --git a/include/commodity.h b/include/commodity.h
index c37576619..d515364e7 100644
--- a/include/commodity.h
+++ b/include/commodity.h
@@ -44,6 +44,7 @@ struct comstr {
     /* initial part must match struct empobj */
     short ef_type;
     short com_uid;
+    unsigned com_seqno;
     time_t com_timestamp;
     natid com_owner;
     /* end of part matching struct empobj */
diff --git a/include/empobj.h b/include/empobj.h
index 2610c18ee..63931c106 100644
--- a/include/empobj.h
+++ b/include/empobj.h
@@ -57,6 +57,7 @@ struct empobj {
      */
     short ef_type;
     short uid;
+    unsigned seqno;
     time_t timestamp;
     /* end of part matching struct emptypedstr */
     natid own;		/* valid if EFF_OWNER is in table's flags */
diff --git a/include/file.h b/include/file.h
index 795177840..9d724f658 100644
--- a/include/file.h
+++ b/include/file.h
@@ -67,6 +67,7 @@ struct empfile {
 struct emptypedstr {
     short ef_type;
     short uid;
+    unsigned seqno;
     time_t timestamp;
 };
 
@@ -187,6 +188,7 @@ extern int ef_close(int);
 extern int ef_flush(int);
 extern void ef_blank(int, int, void *);
 extern int ef_write(int, int, void *);
+extern void ef_set_uid(int, void *, int);
 extern int ef_extend(int, int);
 extern int ef_ensure_space(int, int, int);
 extern int ef_truncate(int, int);
diff --git a/include/game.h b/include/game.h
index 8a52509c5..1a343c7f9 100644
--- a/include/game.h
+++ b/include/game.h
@@ -40,6 +40,7 @@ struct gamestr {
     /* initial part must match struct empobj */
     short ef_type;
     short game_uid;
+    unsigned game_seqno;
     time_t game_timestamp;
     /* end of part matching struct empobj */
     char game_upd_disable;	/* updates disabled? */
diff --git a/include/land.h b/include/land.h
index feb47c6ae..73ca0b827 100644
--- a/include/land.h
+++ b/include/land.h
@@ -51,6 +51,7 @@ struct lndstr {
     /* initial part must match struct empobj */
     short ef_type;
     short lnd_uid;		/* unit id (land unit) */
+    unsigned lnd_seqno;
     time_t lnd_timestamp;	/* Last time this unit was touched */
     natid lnd_own;		/* owner's country num */
     coord lnd_x;		/* x location in abs coords */
diff --git a/include/loan.h b/include/loan.h
index 542af6c83..d18c4d88a 100644
--- a/include/loan.h
+++ b/include/loan.h
@@ -44,6 +44,7 @@ struct lonstr {
     /* initial part must match struct empobj */
     short ef_type;
     short l_uid;
+    unsigned l_seqno;
     time_t l_timestamp;
     /* end of part matching struct empobj */
     natid l_loner;		/* loan shark */
diff --git a/include/lost.h b/include/lost.h
index c371f936c..1bb930796 100644
--- a/include/lost.h
+++ b/include/lost.h
@@ -41,6 +41,7 @@ struct loststr {
     /* initial part must match struct empobj */
     short ef_type;
     int lost_uid;
+    unsigned lost_seqno;
     time_t lost_timestamp;	/* When it was lost */
     natid lost_owner;		/* Who lost it */
     /* end of part matching struct empobj */
diff --git a/include/nat.h b/include/nat.h
index b2f2bd5f8..58b8067fc 100644
--- a/include/nat.h
+++ b/include/nat.h
@@ -70,6 +70,7 @@ struct realmstr {
     /* initial part must match struct empobj */
     short ef_type;
     short r_uid;		/* realm table index */
+    unsigned r_seqno;
     time_t r_timestamp;		/* Last time this realm was touched */
     natid r_cnum;		/* country number */
     /* end of part matching struct empobj */
@@ -82,6 +83,7 @@ struct natstr {
     /* initial part must match struct empobj */
     short ef_type;
     short nat_uid;		/* equals nat_cnum */
+    unsigned nat_seqno;
     time_t nat_timestamp;
     natid nat_cnum;		/* our country number */
     /* end of part matching struct empobj */
diff --git a/include/news.h b/include/news.h
index c73611444..5665a92fa 100644
--- a/include/news.h
+++ b/include/news.h
@@ -48,6 +48,7 @@ struct nwsstr {
     /* initial part must match struct empobj */
     short ef_type;
     short nws_uid;
+    unsigned nws_seqno;
     time_t nws_timestamp;
     /* end of part matching struct empobj */
     natid nws_ano;		/* "actor" country # */
diff --git a/include/nuke.h b/include/nuke.h
index 2f7fcdaa1..054cdb4c3 100644
--- a/include/nuke.h
+++ b/include/nuke.h
@@ -44,6 +44,7 @@ struct nukstr {
     /* initial part must match struct empobj */
     short ef_type;
     short nuk_uid;
+    unsigned nuk_seqno;
     time_t nuk_timestamp;	/* Last time this nuke was touched */
     natid nuk_own;
     coord nuk_x, nuk_y;		/* current loc of device */
diff --git a/include/plane.h b/include/plane.h
index 2133f3628..485ebb51e 100644
--- a/include/plane.h
+++ b/include/plane.h
@@ -48,6 +48,7 @@ struct plnstr {
     /* initial part must match struct empobj */
     short ef_type;
     short pln_uid;		/* plane unit id */
+    unsigned pln_seqno;
     time_t pln_timestamp;	/* Last time this plane was touched */
     natid pln_own;		/* owning country */
     coord pln_x;		/* plane x-y */
diff --git a/include/sect.h b/include/sect.h
index d8a109afa..408b1600b 100644
--- a/include/sect.h
+++ b/include/sect.h
@@ -46,6 +46,7 @@ struct sctstr {
     /* initial part must match struct empobj */
     short ef_type;
     short sct_uid;		/* equals XYOFFSET(sct_x, sct_y) */
+    unsigned sct_seqno;
     time_t sct_timestamp;	/* Last time this sector was written to */
     natid sct_own;		/* owner's country num */
     coord sct_x;		/* x coord of sector */
diff --git a/include/ship.h b/include/ship.h
index 1f7fbf8ab..d09a07b0d 100644
--- a/include/ship.h
+++ b/include/ship.h
@@ -65,6 +65,7 @@ struct shpstr {
     /* initial part must match struct empobj */
     short ef_type;
     short shp_uid;		/* unit id (ship #) */
+    unsigned shp_seqno;
     time_t shp_timestamp;	/* Last time this ship was touched. */
     natid shp_own;		/* owner's country num */
     coord shp_x;		/* x location in abs coords */
diff --git a/include/trade.h b/include/trade.h
index 307f990b4..074a77da4 100644
--- a/include/trade.h
+++ b/include/trade.h
@@ -44,6 +44,7 @@ struct trdstr {
     /* initial part must match struct empobj */
     short ef_type;
     short trd_uid;
+    unsigned trd_seqno;
     time_t trd_timestamp;
     natid trd_owner;
     /* end of part matching struct empobj */
diff --git a/include/treaty.h b/include/treaty.h
index d5efd77e6..31491eeff 100644
--- a/include/treaty.h
+++ b/include/treaty.h
@@ -41,6 +41,7 @@ struct trtstr {
     /* initial part must match struct empobj */
     short ef_type;
     short trt_uid;
+    unsigned trt_seqno;
     time_t trt_timestamp;
     /* end of part matching struct empobj */
     natid trt_cna;		/* proposer */
diff --git a/src/lib/commands/edit.c b/src/lib/commands/edit.c
index 52279b841..cabcbabfa 100644
--- a/src/lib/commands/edit.c
+++ b/src/lib/commands/edit.c
@@ -584,7 +584,7 @@ doland(char op, int arg, char *p, struct sctstr *sect)
 	    return RET_SYN;
 	sect->sct_x = newx;
 	sect->sct_y = newy;
-	sect->sct_uid = XYOFFSET(newx, newy);
+	ef_set_uid(EF_SECTOR, &sect, XYOFFSET(newx, newy));
 	break;
     case 'D':
 	if (!sarg_xy(p, &newx, &newy))
@@ -767,7 +767,7 @@ doship(char op, int arg, char *p, struct shpstr *ship)
 	ship->shp_rflags = arg;
 	break;
     case 'U':
-	ship->shp_uid = arg;
+	ef_set_uid(EF_SHIP, ship, arg);
 	break;
     case 'O':
 	if (ship->shp_own)
@@ -871,7 +871,7 @@ dounit(char op, int arg, char *p, struct lndstr *land)
 	land->lnd_land = arg;
 	break;
     case 'U':
-	land->lnd_uid = arg;
+	ef_set_uid(EF_SHIP, land, arg);
 	break;
     case 'O':
 	if (land->lnd_own)
diff --git a/src/lib/commands/swap.c b/src/lib/commands/swap.c
index a28b89913..309977c5e 100644
--- a/src/lib/commands/swap.c
+++ b/src/lib/commands/swap.c
@@ -63,14 +63,14 @@ swaps(void)
     /* change the location of secta to that of sectb */
     secta.sct_x = sectb.sct_x;
     secta.sct_y = sectb.sct_y;
-    secta.sct_uid = sectb.sct_uid;
+    ef_set_uid(EF_SECTOR, &secta, sectb.sct_uid);
     secta.sct_dist_x = sectb.sct_x;
     secta.sct_dist_y = sectb.sct_y;
     secta.sct_coastal = sectb.sct_coastal;
     /* change the location of sectb to where secta was */
     sectb.sct_x = tmp.sct_x;
     sectb.sct_y = tmp.sct_y;
-    sectb.sct_uid = tmp.sct_uid;
+    ef_set_uid(EF_SECTOR, &sectb, tmp.sct_uid);
     sectb.sct_dist_x = tmp.sct_x;
     sectb.sct_dist_y = tmp.sct_y;
     sectb.sct_coastal = tmp.sct_coastal;
diff --git a/src/lib/common/file.c b/src/lib/common/file.c
index 9586bc4dd..ce13d14b5 100644
--- a/src/lib/common/file.c
+++ b/src/lib/common/file.c
@@ -48,7 +48,10 @@
 
 static int ef_realloc_cache(struct empfile *, int);
 static int fillcache(struct empfile *, int);
+static int do_read(struct empfile *, void *, int, int);
 static int do_write(struct empfile *, void *, int, int, time_t);
+static int get_seqno(struct empfile *, int);
+static void new_seqno(struct empfile *, void *);
 static void do_blank(struct empfile *, void *, int, int);
 
 /*
@@ -300,11 +303,28 @@ ef_read(int type, int id, void *into)
  */
 static int
 fillcache(struct empfile *ep, int id)
+{
+    int ret;
+
+    if (CANT_HAPPEN(!ep->cache))
+	return -1;
+
+    ret = do_read(ep, ep->cache, id, MIN(ep->csize, ep->fids - id));
+    if (ret >= 0) {
+	/* cache changed */
+	ep->baseid = id;
+	ep->cids = ret;
+    }
+    return ret;
+}
+
+static int
+do_read(struct empfile *ep, void *buf, int id, int count)
 {
     int n, ret;
     char *p;
 
-    if (CANT_HAPPEN(ep->fd < 0 || !ep->cache))
+    if (CANT_HAPPEN(ep->fd < 0 || id < 0 || count < 0))
 	return -1;
 
     if (lseek(ep->fd, id * ep->size, SEEK_SET) == (off_t)-1) {
@@ -313,21 +333,21 @@ fillcache(struct empfile *ep, int id)
 	return -1;
     }
 
-    p = ep->cache;
-    n = MIN(ep->csize, ep->fids - id) * ep->size;
+    p = buf;
+    n = count * ep->size;
     while (n > 0) {
 	ret = read(ep->fd, p, n);
 	if (ret < 0) {
 	    if (errno != EINTR) {
 		logerror("Error reading %s elt %d (%s)",
 			 ep->file,
-			 id + (int)((p - ep->cache) / ep->size),
+			 id + (int)((p - (char *)buf) / ep->size),
 			 strerror(errno));
 		break;
 	    }
 	} else if (ret == 0) {
 	    logerror("Unexpected EOF reading %s elt %d",
-		     ep->file, id + (int)((p - ep->cache) / ep->size));
+		     ep->file, id + (int)((p - (char *)buf) / ep->size));
 	    break;
 	} else {
 	    p += ret;
@@ -335,12 +355,7 @@ fillcache(struct empfile *ep, int id)
 	}
     }
 
-    if (p == ep->cache)
-	return -1;		/* nothing read, old cache still ok */
-
-    ep->baseid = id;
-    ep->cids = (p - ep->cache) / ep->size;
-    return ep->cids;
+    return (p - (char *)buf) / ep->size;
 }
 
 /*
@@ -425,6 +440,7 @@ ef_write(int type, int id, void *from)
 	ep->prewrite(id, from);
     if (CANT_HAPPEN((ep->flags & EFF_MEM) ? id >= ep->fids : id > ep->fids))
 	return 0;		/* not implemented */
+    new_seqno(ep, from);
     if (!(ep->flags & EFF_PRIVATE)) {
 	if (do_write(ep, from, id, 1, time(NULL)) < 0)
 	    return 0;
@@ -442,6 +458,68 @@ ef_write(int type, int id, void *from)
     return 1;
 }
 
+void
+ef_set_uid(int type, void *buf, int uid)
+{
+    struct emptypedstr *elt;
+    struct empfile *ep;
+
+    if (ef_check(type) < 0)
+	return;
+    ep = &empfile[type];
+    if (!(ep->flags & EFF_TYPED))
+	return;
+    elt = buf;
+    if (elt->uid == uid)
+	return;
+    elt->uid = uid;
+    elt->seqno = get_seqno(ep, uid);
+}
+
+static int
+get_seqno(struct empfile *ep, int id)
+{
+    struct emptypedstr *elt;
+
+    if (!(ep->flags & EFF_TYPED))
+	return 0;
+    if (id < 0 || id >= ep->fids)
+	return 0;
+    if (id >= ep->baseid && id < ep->baseid + ep->cids)
+	elt = (void *)(ep->cache + (id - ep->baseid) * ep->size);
+    else {
+	/* need a buffer, steal last cache slot */
+	if (ep->cids == ep->csize)
+	    ep->cids--;
+	elt = (void *)(ep->cache + ep->cids * ep->size);
+	if (do_read(ep, elt, id, 1) < 0)
+	    return 0;		/* deep trouble */
+    }
+    return elt->seqno;
+}
+
+static void
+new_seqno(struct empfile *ep, void *buf)
+{
+    struct emptypedstr *elt = buf;
+    unsigned old_seqno;
+
+    if (!(ep->flags & EFF_TYPED))
+	return;
+    old_seqno = get_seqno(ep, elt->uid);
+#if 0
+    if (CANT_HAPPEN(old_seqno != elt->seqno))
+	old_seqno = MAX(old_seqno, elt->seqno);
+#else
+    if (old_seqno != elt->seqno) {
+	logerror("seqno mismatch ef_type=%d uid=%d: %d!=%d",
+		 ep->uid, elt->uid, old_seqno, elt->seqno);
+	old_seqno = MAX(old_seqno, elt->seqno);
+    }
+#endif
+    elt->seqno = old_seqno + 1;
+}
+
 /*
  * Extend table TYPE by COUNT elements.
  * Any pointers obtained from ef_ptr() become invalid.
@@ -504,9 +582,17 @@ ef_extend(int type, int count)
 void
 ef_blank(int type, int id, void *buf)
 {
+    struct empfile *ep;
+    struct emptypedstr *elt;
+
     if (ef_check(type) < 0)
 	return;
-    do_blank(&empfile[type], buf, id, 1);
+    ep = &empfile[type];
+    do_blank(ep, buf, id, 1);
+    if (ep->flags & EFF_TYPED) {
+	elt = buf;
+	elt->seqno = get_seqno(ep, elt->uid);
+    }
 }
 
 /*
diff --git a/src/lib/subs/nreport.c b/src/lib/subs/nreport.c
index 8a53cbeed..2dffb2681 100644
--- a/src/lib/subs/nreport.c
+++ b/src/lib/subs/nreport.c
@@ -111,7 +111,7 @@ delete_old_news(void)
     for (j = 0; getnews(i + j, &news); j++) {
 	if (news.nws_vrb == 0)
 	    break;
-	news.nws_uid = j;
+	ef_set_uid(EF_NEWS, &news, j);
 	putnews(j, &news);
     }
     CANT_HAPPEN(i + j != news_tail);
diff --git a/src/util/files.c b/src/util/files.c
index 4618ba6ef..a7c802b7f 100644
--- a/src/util/files.c
+++ b/src/util/files.c
@@ -155,6 +155,7 @@ main(int argc, char *argv[])
     for (i = 1; i < MAXNOC; i++) {
 	nat.ef_type = EF_NATION;
 	nat.nat_cnum = nat.nat_uid = i;
+	nat.nat_seqno = 0;
 	putnat((&nat));
     }
     memset(&realm, 0, sizeof(realm));
@@ -164,6 +165,7 @@ main(int argc, char *argv[])
 	for (j = 0; j < MAXNOR; j++) {
 	    realm.r_realm = j;
 	    realm.r_uid = (i * MAXNOR) + j;
+	    realm.r_seqno = 0;
 	    putrealm(&realm);
 	}
     }
@@ -209,6 +211,7 @@ file_sct_init(coord x, coord y, struct sctstr *ptr)
 
     sp->ef_type = EF_SECTOR;
     sp->sct_uid = XYOFFSET(x, y);
+    sp->sct_seqno = 0;
     sp->sct_x = x;
     sp->sct_y = y;
     sp->sct_dist_x = x;
-- 
2.43.0