1 /*-
2 * Copyright (c) 2006, Maxime Henrion <mux@FreeBSD.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD$
27 */
28 #include <sys/types.h>
29
30 #include <assert.h>
31 #include <grp.h>
32 #include <pthread.h>
33 #include <pwd.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "idcache.h"
38 #include "misc.h"
39
40 /*
41 * Constants and data structures used to implement the thread-safe
42 * group and password file caches. Cache sizes must be prime.
43 */
44 #define UIDTONAME_SZ 317 /* Size of uid -> user name cache */
45 #define NAMETOUID_SZ 317 /* Size of user name -> uid cache */
46 #define GIDTONAME_SZ 317 /* Size of gid -> group name cache */
47 #define NAMETOGID_SZ 317 /* Size of group name -> gid cache */
48
49 /* Node structures used to cache lookups. */
50 struct uidc {
51 char *name; /* user name */
52 uid_t uid; /* cached uid */
53 int valid; /* is this a valid or a miss entry */
54 struct uidc *next; /* for collisions */
55 };
56
57 struct gidc {
58 char *name; /* group name */
59 gid_t gid; /* cached gid */
60 int valid; /* is this a valid or a miss entry */
61 struct gidc *next; /* for collisions */
62 };
63
64 static struct uidc **uidtoname; /* uid to user name cache */
65 static struct gidc **gidtoname; /* gid to group name cache */
66 static struct uidc **nametouid; /* user name to uid cache */
67 static struct gidc **nametogid; /* group name to gid cache */
68
69 static pthread_mutex_t uid_mtx;
70 static pthread_mutex_t gid_mtx;
71
72 static void uid_lock(void);
73 static void uid_unlock(void);
74 static void gid_lock(void);
75 static void gid_unlock(void);
76
77 static uint32_t hash(const char *);
78
79 /* A 32-bit version of Peter Weinberger's (PJW) hash algorithm,
80 as used by ELF for hashing function names. */
81 static uint32_t
hash(const char * name)82 hash(const char *name)
83 {
84 uint32_t g, h;
85
86 h = 0;
87 while(*name != '\0') {
88 h = (h << 4) + *name++;
89 if ((g = h & 0xF0000000)) {
90 h ^= g >> 24;
91 h &= 0x0FFFFFFF;
92 }
93 }
94 return (h);
95 }
96
97 static void
uid_lock(void)98 uid_lock(void)
99 {
100 int error;
101
102 error = pthread_mutex_lock(&uid_mtx);
103 assert(!error);
104 }
105
106 static void
uid_unlock(void)107 uid_unlock(void)
108 {
109 int error;
110
111 error = pthread_mutex_unlock(&uid_mtx);
112 assert(!error);
113 }
114
115 static void
gid_lock(void)116 gid_lock(void)
117 {
118 int error;
119
120 error = pthread_mutex_lock(&gid_mtx);
121 assert(!error);
122 }
123
124 static void
gid_unlock(void)125 gid_unlock(void)
126 {
127 int error;
128
129 error = pthread_mutex_unlock(&gid_mtx);
130 assert(!error);
131 }
132
133 static void
uidc_insert(struct uidc ** tbl,struct uidc * uidc,uint32_t key)134 uidc_insert(struct uidc **tbl, struct uidc *uidc, uint32_t key)
135 {
136
137 uidc->next = tbl[key];
138 tbl[key] = uidc;
139 }
140
141 static void
gidc_insert(struct gidc ** tbl,struct gidc * gidc,uint32_t key)142 gidc_insert(struct gidc **tbl, struct gidc *gidc, uint32_t key)
143 {
144
145 gidc->next = tbl[key];
146 tbl[key] = gidc;
147 }
148
149 /* Return the user name for this uid, or NULL if it's not found. */
150 char *
getuserbyid(uid_t uid)151 getuserbyid(uid_t uid)
152 {
153 struct passwd *pw;
154 struct uidc *uidc, *uidc2;
155 uint32_t key, key2;
156
157 key = uid % UIDTONAME_SZ;
158 uid_lock();
159 uidc = uidtoname[key];
160 while (uidc != NULL) {
161 if (uidc->uid == uid)
162 break;
163 uidc = uidc->next;
164 }
165
166 if (uidc == NULL) {
167 /* We didn't find this uid, look it up and add it. */
168 uidc = xmalloc(sizeof(struct uidc));
169 uidc->uid = uid;
170 pw = getpwuid(uid);
171 if (pw != NULL) {
172 /* This uid is in the password file. */
173 uidc->name = xstrdup(pw->pw_name);
174 uidc->valid = 1;
175 /* Also add it to the name -> gid table. */
176 uidc2 = xmalloc(sizeof(struct uidc));
177 uidc2->uid = uid;
178 uidc2->name = uidc->name; /* We reuse the pointer. */
179 uidc2->valid = 1;
180 key2 = hash(uidc->name) % NAMETOUID_SZ;
181 uidc_insert(nametouid, uidc2, key2);
182 } else {
183 /* Add a miss entry for this uid. */
184 uidc->name = NULL;
185 uidc->valid = 0;
186 }
187 uidc_insert(uidtoname, uidc, key);
188 }
189 /* It is safe to unlock here since the cache structure
190 is not going to get freed or changed. */
191 uid_unlock();
192 return (uidc->name);
193 }
194
195 /* Return the group name for this gid, or NULL if it's not found. */
196 char *
getgroupbyid(gid_t gid)197 getgroupbyid(gid_t gid)
198 {
199 struct group *gr;
200 struct gidc *gidc, *gidc2;
201 uint32_t key, key2;
202
203 key = gid % GIDTONAME_SZ;
204 gid_lock();
205 gidc = gidtoname[key];
206 while (gidc != NULL) {
207 if (gidc->gid == gid)
208 break;
209 gidc = gidc->next;
210 }
211
212 if (gidc == NULL) {
213 /* We didn't find this gid, look it up and add it. */
214 gidc = xmalloc(sizeof(struct gidc));
215 gidc->gid = gid;
216 gr = getgrgid(gid);
217 if (gr != NULL) {
218 /* This gid is in the group file. */
219 gidc->name = xstrdup(gr->gr_name);
220 gidc->valid = 1;
221 /* Also add it to the name -> gid table. */
222 gidc2 = xmalloc(sizeof(struct gidc));
223 gidc2->gid = gid;
224 gidc2->name = gidc->name; /* We reuse the pointer. */
225 gidc2->valid = 1;
226 key2 = hash(gidc->name) % NAMETOGID_SZ;
227 gidc_insert(nametogid, gidc2, key2);
228 } else {
229 /* Add a miss entry for this gid. */
230 gidc->name = NULL;
231 gidc->valid = 0;
232 }
233 gidc_insert(gidtoname, gidc, key);
234 }
235 /* It is safe to unlock here since the cache structure
236 is not going to get freed or changed. */
237 gid_unlock();
238 return (gidc->name);
239 }
240
241 /* Finds the uid for this user name. If it's found, the gid is stored
242 in *uid and 0 is returned. Otherwise, -1 is returned. */
243 int
getuidbyname(const char * name,uid_t * uid)244 getuidbyname(const char *name, uid_t *uid)
245 {
246 struct passwd *pw;
247 struct uidc *uidc, *uidc2;
248 uint32_t key, key2;
249
250 uid_lock();
251 key = hash(name) % NAMETOUID_SZ;
252 uidc = nametouid[key];
253 while (uidc != NULL) {
254 if (strcmp(uidc->name, name) == 0)
255 break;
256 uidc = uidc->next;
257 }
258
259 if (uidc == NULL) {
260 uidc = xmalloc(sizeof(struct uidc));
261 uidc->name = xstrdup(name);
262 pw = getpwnam(name);
263 if (pw != NULL) {
264 /* This user name is in the password file. */
265 uidc->valid = 1;
266 uidc->uid = pw->pw_uid;
267 /* Also add it to the uid -> name table. */
268 uidc2 = xmalloc(sizeof(struct uidc));
269 uidc2->name = uidc->name; /* We reuse the pointer. */
270 uidc2->uid = uidc->uid;
271 uidc2->valid = 1;
272 key2 = uidc2->uid % UIDTONAME_SZ;
273 uidc_insert(uidtoname, uidc2, key2);
274 } else {
275 /* Add a miss entry for this user name. */
276 uidc->valid = 0;
277 uidc->uid = (uid_t)-1; /* Should not be accessed. */
278 }
279 uidc_insert(nametouid, uidc, key);
280 }
281 /* It is safe to unlock here since the cache structure
282 is not going to get freed or changed. */
283 uid_unlock();
284 if (!uidc->valid)
285 return (-1);
286 *uid = uidc->uid;
287 return (0);
288 }
289
290 /* Finds the gid for this group name. If it's found, the gid is stored
291 in *gid and 0 is returned. Otherwise, -1 is returned. */
292 int
getgidbyname(const char * name,gid_t * gid)293 getgidbyname(const char *name, gid_t *gid)
294 {
295 struct group *gr;
296 struct gidc *gidc, *gidc2;
297 uint32_t key, key2;
298
299 gid_lock();
300 key = hash(name) % NAMETOGID_SZ;
301 gidc = nametogid[key];
302 while (gidc != NULL) {
303 if (strcmp(gidc->name, name) == 0)
304 break;
305 gidc = gidc->next;
306 }
307
308 if (gidc == NULL) {
309 gidc = xmalloc(sizeof(struct gidc));
310 gidc->name = xstrdup(name);
311 gr = getgrnam(name);
312 if (gr != NULL) {
313 /* This group name is in the group file. */
314 gidc->gid = gr->gr_gid;
315 gidc->valid = 1;
316 /* Also add it to the gid -> name table. */
317 gidc2 = xmalloc(sizeof(struct gidc));
318 gidc2->name = gidc->name; /* We reuse the pointer. */
319 gidc2->gid = gidc->gid;
320 gidc2->valid = 1;
321 key2 = gidc2->gid % GIDTONAME_SZ;
322 gidc_insert(gidtoname, gidc2, key2);
323 } else {
324 /* Add a miss entry for this group name. */
325 gidc->gid = (gid_t)-1; /* Should not be accessed. */
326 gidc->valid = 0;
327 }
328 gidc_insert(nametogid, gidc, key);
329 }
330 /* It is safe to unlock here since the cache structure
331 is not going to get freed or changed. */
332 gid_unlock();
333 if (!gidc->valid)
334 return (-1);
335 *gid = gidc->gid;
336 return (0);
337 }
338
339 /* Initialize the cache structures. */
340 void
idcache_init(void)341 idcache_init(void)
342 {
343
344 pthread_mutex_init(&uid_mtx, NULL);
345 pthread_mutex_init(&gid_mtx, NULL);
346 uidtoname = xmalloc(UIDTONAME_SZ * sizeof(struct uidc *));
347 gidtoname = xmalloc(GIDTONAME_SZ * sizeof(struct gidc *));
348 nametouid = xmalloc(NAMETOUID_SZ * sizeof(struct uidc *));
349 nametogid = xmalloc(NAMETOGID_SZ * sizeof(struct gidc *));
350 memset(uidtoname, 0, UIDTONAME_SZ * sizeof(struct uidc *));
351 memset(gidtoname, 0, GIDTONAME_SZ * sizeof(struct gidc *));
352 memset(nametouid, 0, NAMETOUID_SZ * sizeof(struct uidc *));
353 memset(nametogid, 0, NAMETOGID_SZ * sizeof(struct gidc *));
354 }
355
356 /* Cleanup the cache structures. */
357 void
idcache_fini(void)358 idcache_fini(void)
359 {
360 struct uidc *uidc, *uidc2;
361 struct gidc *gidc, *gidc2;
362 size_t i;
363
364 for (i = 0; i < UIDTONAME_SZ; i++) {
365 uidc = uidtoname[i];
366 while (uidc != NULL) {
367 if (uidc->name != NULL) {
368 assert(uidc->valid);
369 free(uidc->name);
370 }
371 uidc2 = uidc->next;
372 free(uidc);
373 uidc = uidc2;
374 }
375 }
376 free(uidtoname);
377 for (i = 0; i < NAMETOUID_SZ; i++) {
378 uidc = nametouid[i];
379 while (uidc != NULL) {
380 assert(uidc->name != NULL);
381 /* If it's a valid entry, it has been added to both the
382 uidtoname and nametouid tables, and the name pointer
383 has been reused for both entries. Thus, the name
384 pointer has already been freed in the loop above. */
385 if (!uidc->valid)
386 free(uidc->name);
387 uidc2 = uidc->next;
388 free(uidc);
389 uidc = uidc2;
390 }
391 }
392 free(nametouid);
393 for (i = 0; i < GIDTONAME_SZ; i++) {
394 gidc = gidtoname[i];
395 while (gidc != NULL) {
396 if (gidc->name != NULL) {
397 assert(gidc->valid);
398 free(gidc->name);
399 }
400 gidc2 = gidc->next;
401 free(gidc);
402 gidc = gidc2;
403 }
404 }
405 free(gidtoname);
406 for (i = 0; i < NAMETOGID_SZ; i++) {
407 gidc = nametogid[i];
408 while (gidc != NULL) {
409 assert(gidc->name != NULL);
410 /* See above comment. */
411 if (!gidc->valid)
412 free(gidc->name);
413 gidc2 = gidc->next;
414 free(gidc);
415 gidc = gidc2;
416 }
417 }
418 free(nametogid);
419 pthread_mutex_destroy(&uid_mtx);
420 pthread_mutex_destroy(&gid_mtx);
421 }
422