ref: 9b14a2f3b443a8bd615551cb2320829d134650bd
parent: ce768a70c40c96c6e6dbd1018306a122a4eeec43
author: kvik <kvik@a-b.xyz>
date: Sat May 29 08:11:49 EDT 2021
Fix merge
--- /dev/null
+++ b/qmap.c
@@ -1,0 +1,155 @@
+/*
+ * Encode (Dir.type, Dir.dev, Dir.Qid.path) into Qid.path.
+ * We do this by making an educated guess on how the input
+ * bits are going to be laid out in the common case which
+ * allows a direct encoding scheme to be used for most
+ * files; otherwise we must resort to storing a full map
+ * entry into a table.
+ *
+ * The bits of output Qid.path are assigned as follows:
+ *
+ * For directly encoded paths the bit 63 is set to zero,
+ * otherwise it is set to one. This splits the path space
+ * in half.
+ *
+ * For table-mapped paths the rest of the bits are simply
+ * counting from 0 to 2^63-1. There is no relation between
+ * input and output bits; the entire input tuple and the
+ * output Qid.path are stored into a map.
+ *
+ * The direct encoding scheme works by assuming several
+ * properties on the structure of input tuple fields.
+ * First, it is evident that the Plan 9 kernel uses a very
+ * small number of device types (Dir.type), the most common
+ * of which is devmnt (M). Furthermore, the file servers
+ * mounted through this type are the ones serving the most
+ * files and are most likely to be served by unionfs.
+ * Therefore we dedicate the entire space to this type
+ * of device.
+ * Secondly, the device instance (Dir.dev) is always a
+ * simple counter value, as are the Qid.paths of most
+ * file servers. This lets us simply drop some number
+ * of upper bits from each to make them fit into our space.
+ *
+ * We do this as follows:
+ * - 32-bit Dir.dev is reduced to its lower 28 bits.
+ * - 64-bit Dir.qid.path is reduced to its lower 35 bits.
+ *
+ * If type isn't M, or if the reduction of dev or path
+ * results in a loss of information, that is, if some of
+ * the cut bits are set; then the tuple must be table-mapped.
+ *
+ * The amount of bits allocated to each encoded field
+ * was determined by assuming that it is not very common for
+ * most file servers to host many billions of files, while a
+ * busy server will easily make many millions of mounts during
+ * its uptime.
+ * Making the kernel reuse device instance numbers could
+ * be done to help the matter significantly, letting us use
+ * almost the entire space just for paths.
+ */
+
+#include <u.h>
+#include <libc.h>
+#include <thread.h>
+#include "unionfs.h"
+
+#define mask(v) ((1ull << v) - 1)
+
+enum {+ Qmapsize = 1024,
+
+ MapBit = 63,
+ DevBits = 28,
+ PathBits = 35,
+};
+
+typedef struct Qmap Qmap;
+struct Qmap {+ ushort type;
+ uint dev;
+ uvlong path;
+ uvlong qpath;
+ Qmap *next;
+};
+
+RWLock qidmaplock;
+Qmap *qidmap[Qmapsize];
+
+uvlong
+qhash(Dir *d)
+{+ uvlong h;
+ usize i;
+ uchar *key;
+
+ h = 14695981039346656037ULL;
+ key = (uchar*)&d->type;
+ for(i = 0; i < sizeof(d->type); i++){+ h ^= key[i];
+ h *= 1099511628211ULL;
+ }
+ key = (uchar*)&d->dev;
+ for(i = 0; i < sizeof(d->dev); i++){+ h ^= key[i];
+ h *= 1099511628211ULL;
+ }
+ key = (uchar*)&d->qid.path;
+ for(i = 0; i < sizeof(d->qid.path); i++){+ h ^= key[i];
+ h *= 1099511628211ULL;
+ }
+ return h;
+}
+
+Qid
+qencode(Dir *d)
+{+ ushort type;
+ uint dev;
+ uvlong path;
+ Qid qid;
+
+ qid.vers = d->qid.vers;
+ qid.type = d->qid.type;
+ type = d->type;
+ dev = d->dev;
+ path = d->qid.path;
+ if(type == 'M'
+ && (dev & ~mask(DevBits)) == 0
+ && (path & ~mask(PathBits)) == 0){+ qid.path = 0
+ | (0ull << MapBit)
+ | ((uvlong)dev) << (63 - DevBits)
+ | path;
+ return qid;
+ }
+
+ static uvlong qpath = 0;
+ Qmap *q;
+ uvlong h;
+
+ h = qhash(d) % Qmapsize;
+ rlock(&qidmaplock);
+ for(q = qidmap[h]; q != nil; q = q->next){+ if(q->type == type && q->dev == dev && q->path == path){+ qid.path = q->qpath;
+ runlock(&qidmaplock);
+ return qid;
+ }
+ }
+ runlock(&qidmaplock);
+ q = emalloc(sizeof(Qmap));
+ q->type = type;
+ q->dev = dev;
+ q->path = path;
+ wlock(&qidmaplock);
+ q->qpath = 0
+ | (1ull << MapBit)
+ | qpath++;
+ q->next = qidmap[h];
+ qidmap[h] = q;
+ qid.path = q->qpath;
+ wunlock(&qidmaplock);
+ return qid;
+}