ref: 8c414226dd80caed40c8e3befe96a7cc5553d7aa
dir: /qmap.c/
/*
* 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;
}