ref: c1eed337afadb15156a5364767c3e3755586e537
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 "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; }