lib/ino-map.c

   1 /* Map an ino_t inode number to a small integer.
   2
   3    Copyright 2009-2024 Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* written by Paul Eggert and Jim Meyering */
  19
  20 #include <config.h>
  21 #include "ino-map.h"
  22
  23 #include "hash.h"
  24
  25 #include <limits.h>
  26 #include <stdlib.h>
  27
  28 /* A pair that maps an inode number to a mapped inode number; the
  29    latter is a small unique ID for the former.  */
  30 struct ino_map_ent
  31 {
  32   ino_t ino;
  33   size_t mapped_ino;
  34 };
  35
  36 /* A table that manages and indexes these pairs.  */
  37 struct ino_map
  38 {
  39   /* A table of KEY,VAL pairs, where KEY is the raw ino_t value and
  40      VAL is the small number that it maps to.  */
  41   struct hash_table *map;
  42
  43   /* The next mapped inode number to hand out.  */
  44   size_t next_mapped_ino;
  45
  46   /* Cache of the most recently allocated and otherwise-unused storage
  47      for probing the table.  */
  48   struct ino_map_ent *probe;
  49 };
  50
  51 /* Hash an inode map entry.  */
  52 static size_t
  53 ino_hash (void const *x, size_t table_size)
  54 {
  55   struct ino_map_ent const *p = x;
  56   ino_t ino = p->ino;
  57
  58   /* When INO is wider than size_t, exclusive-OR the words of INO into H.
  59      This avoids loss of info, without applying % to the wider type,
  60      which could be quite slow on some systems.  */
  61   size_t h = ino;
  62   unsigned int i;
  63   unsigned int n_words = sizeof ino / sizeof h + (sizeof ino % sizeof h != 0);
  64   for (i = 1; i < n_words; i++)
  65     h ^= ino >> CHAR_BIT * sizeof h * i;
  66
  67   return h % table_size;
  68 }
  69
  70 /* Return true if two inode map entries are the same.  */
  71 static bool
  72 ino_compare (void const *x, void const *y)
  73 {
  74   struct ino_map_ent const *a = x;
  75   struct ino_map_ent const *b = y;
  76   return a->ino == b->ino;
  77 }
  78
  79 /* Allocate an inode map that will hand out integers starting with
  80    NEXT_MAPPED_INO.  Return NULL if memory is exhausted.  */
  81 struct ino_map *
  82 ino_map_alloc (size_t next_mapped_ino)
  83 {
  84   struct ino_map *im = malloc (sizeof *im);
  85
  86   if (im)
  87     {
  88       enum { INITIAL_INO_MAP_TABLE_SIZE = 1021 };
  89       im->map = hash_initialize (INITIAL_INO_MAP_TABLE_SIZE, NULL,
  90                                  ino_hash, ino_compare, free);
  91       if (! im->map)
  92         {
  93           free (im);
  94           return NULL;
  95         }
  96       im->next_mapped_ino = next_mapped_ino;
  97       im->probe = NULL;
  98     }
  99
 100   return im;
 101 }
 102
 103 /* Free an inode map.  */
 104 void
 105 ino_map_free (struct ino_map *map)
 106 {
 107   hash_free (map->map);
 108   free (map->probe);
 109   free (map);
 110 }
 111
 112
 113 /* Insert into MAP the inode number INO if it's not there already,
 114    and return its nonnegative mapped inode number.
 115    If INO is already in MAP, return the existing mapped inode number.
 116    Return INO_MAP_INSERT_FAILURE on memory or counter exhaustion.  */
 117 size_t
 118 ino_map_insert (struct ino_map *im, ino_t ino)
 119 {
 120   struct ino_map_ent *ent;
 121
 122   /* Find space for the probe, reusing the cache if available.  */
 123   struct ino_map_ent *probe = im->probe;
 124   if (probe)
 125     {
 126       /* If repeating a recent query, return the cached result.   */
 127       if (probe->ino == ino)
 128         return probe->mapped_ino;
 129     }
 130   else
 131     {
 132       im->probe = probe = malloc (sizeof *probe);
 133       if (! probe)
 134         return INO_MAP_INSERT_FAILURE;
 135     }
 136
 137   probe->ino = ino;
 138   ent = hash_insert (im->map, probe);
 139   if (! ent)
 140     return INO_MAP_INSERT_FAILURE;
 141
 142   if (ent != probe)
 143     {
 144       /* Use the existing entry.  */
 145       probe->mapped_ino = ent->mapped_ino;
 146     }
 147   else
 148     {
 149       /* If adding 1 to map->next_mapped_ino would cause it to
 150          overflow to zero, then it must equal INO_MAP_INSERT_FAILURE,
 151          which is the value that should be returned in that case.
 152          Verify that this works.  */
 153       static_assert (INO_MAP_INSERT_FAILURE + 1 == 0);
 154
 155       /* Prepare to allocate a new probe next time; this one is in use.  */
 156       im->probe = NULL;
 157
 158       /* INO is new; allocate a mapped inode number for it.  */
 159       probe->mapped_ino = im->next_mapped_ino++;
 160     }
 161
 162   return probe->mapped_ino;
 163 }