usr.bin/csup/idcache.c

   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
  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
  98 uid_lock(void)
  99 {
 100         int error;
 101
 102         error = pthread_mutex_lock(&uid_mtx);
 103         assert(!error);
 104 }
 105
 106 static 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
 116 gid_lock(void)
 117 {
 118         int error;
 119
 120         error = pthread_mutex_lock(&gid_mtx);
 121         assert(!error);
 122 }
 123
 124 static 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
 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
 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 *
 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 *
 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
 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
 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
 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
 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 }