CacheFiles: A cache that backs onto a mounted filesystem
[linux-2.6.git] / fs / cachefiles / key.c
1 /* Key to pathname encoder
2  *
3  * Copyright (C) 2007 Red Hat, Inc. All Rights Reserved.
4  * Written by David Howells (dhowells@redhat.com)
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public Licence
8  * as published by the Free Software Foundation; either version
9  * 2 of the Licence, or (at your option) any later version.
10  */
11
12 #include <linux/slab.h>
13 #include "internal.h"
14
15 static const char cachefiles_charmap[64] =
16         "0123456789"                    /* 0 - 9 */
17         "abcdefghijklmnopqrstuvwxyz"    /* 10 - 35 */
18         "ABCDEFGHIJKLMNOPQRSTUVWXYZ"    /* 36 - 61 */
19         "_-"                            /* 62 - 63 */
20         ;
21
22 static const char cachefiles_filecharmap[256] = {
23         /* we skip space and tab and control chars */
24         [33 ... 46] = 1,                /* '!' -> '.' */
25         /* we skip '/' as it's significant to pathwalk */
26         [48 ... 127] = 1,               /* '0' -> '~' */
27 };
28
29 /*
30  * turn the raw key into something cooked
31  * - the raw key should include the length in the two bytes at the front
32  * - the key may be up to 514 bytes in length (including the length word)
33  *   - "base64" encode the strange keys, mapping 3 bytes of raw to four of
34  *     cooked
35  *   - need to cut the cooked key into 252 char lengths (189 raw bytes)
36  */
37 char *cachefiles_cook_key(const u8 *raw, int keylen, uint8_t type)
38 {
39         unsigned char csum, ch;
40         unsigned int acc;
41         char *key;
42         int loop, len, max, seg, mark, print;
43
44         _enter(",%d", keylen);
45
46         BUG_ON(keylen < 2 || keylen > 514);
47
48         csum = raw[0] + raw[1];
49         print = 1;
50         for (loop = 2; loop < keylen; loop++) {
51                 ch = raw[loop];
52                 csum += ch;
53                 print &= cachefiles_filecharmap[ch];
54         }
55
56         if (print) {
57                 /* if the path is usable ASCII, then we render it directly */
58                 max = keylen - 2;
59                 max += 2;       /* two base64'd length chars on the front */
60                 max += 5;       /* @checksum/M */
61                 max += 3 * 2;   /* maximum number of segment dividers (".../M")
62                                  * is ((514 + 251) / 252) = 3
63                                  */
64                 max += 1;       /* NUL on end */
65         } else {
66                 /* calculate the maximum length of the cooked key */
67                 keylen = (keylen + 2) / 3;
68
69                 max = keylen * 4;
70                 max += 5;       /* @checksum/M */
71                 max += 3 * 2;   /* maximum number of segment dividers (".../M")
72                                  * is ((514 + 188) / 189) = 3
73                                  */
74                 max += 1;       /* NUL on end */
75         }
76
77         max += 1;       /* 2nd NUL on end */
78
79         _debug("max: %d", max);
80
81         key = kmalloc(max, GFP_KERNEL);
82         if (!key)
83                 return NULL;
84
85         len = 0;
86
87         /* build the cooked key */
88         sprintf(key, "@%02x%c+", (unsigned) csum, 0);
89         len = 5;
90         mark = len - 1;
91
92         if (print) {
93                 acc = *(uint16_t *) raw;
94                 raw += 2;
95
96                 key[len + 1] = cachefiles_charmap[acc & 63];
97                 acc >>= 6;
98                 key[len] = cachefiles_charmap[acc & 63];
99                 len += 2;
100
101                 seg = 250;
102                 for (loop = keylen; loop > 0; loop--) {
103                         if (seg <= 0) {
104                                 key[len++] = '\0';
105                                 mark = len;
106                                 key[len++] = '+';
107                                 seg = 252;
108                         }
109
110                         key[len++] = *raw++;
111                         ASSERT(len < max);
112                 }
113
114                 switch (type) {
115                 case FSCACHE_COOKIE_TYPE_INDEX:         type = 'I';     break;
116                 case FSCACHE_COOKIE_TYPE_DATAFILE:      type = 'D';     break;
117                 default:                                type = 'S';     break;
118                 }
119         } else {
120                 seg = 252;
121                 for (loop = keylen; loop > 0; loop--) {
122                         if (seg <= 0) {
123                                 key[len++] = '\0';
124                                 mark = len;
125                                 key[len++] = '+';
126                                 seg = 252;
127                         }
128
129                         acc = *raw++;
130                         acc |= *raw++ << 8;
131                         acc |= *raw++ << 16;
132
133                         _debug("acc: %06x", acc);
134
135                         key[len++] = cachefiles_charmap[acc & 63];
136                         acc >>= 6;
137                         key[len++] = cachefiles_charmap[acc & 63];
138                         acc >>= 6;
139                         key[len++] = cachefiles_charmap[acc & 63];
140                         acc >>= 6;
141                         key[len++] = cachefiles_charmap[acc & 63];
142
143                         ASSERT(len < max);
144                 }
145
146                 switch (type) {
147                 case FSCACHE_COOKIE_TYPE_INDEX:         type = 'J';     break;
148                 case FSCACHE_COOKIE_TYPE_DATAFILE:      type = 'E';     break;
149                 default:                                type = 'T';     break;
150                 }
151         }
152
153         key[mark] = type;
154         key[len++] = 0;
155         key[len] = 0;
156
157         _leave(" = %p %d", key, len);
158         return key;
159 }