lib/ino-map.c

   1 /* Map an ino_t inode number to a small integer.
   2
   3    Copyright 2009-2021 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 #include "verify.h"
  25
  26 #include <limits.h>
  27 #include <stdlib.h>
  28
  29 /* A pair that maps an inode number to a mapped inode number; the
  30    latter is a small unique ID for the former.  */
  31 struct ino_map_ent
  32 {
  33   ino_t ino;
  34   size_t mapped_ino;
  35 };
  36
  37 /* A table that manages and indexes these pairs.  */
  38 struct ino_map
  39 {
  40   /* A table of KEY,VAL pairs, where KEY is the raw ino_t value and
  41      VAL is the small number that it maps to.  */
  42   struct hash_table *map;
  43
  44   /* The next mapped inode number to hand out.  */
  45   size_t next_mapped_ino;
  46
  47   /* Cache of the most recently allocated and otherwise-unused storage
  48      for probing the table.  */
  49   struct ino_map_ent *probe;
  50 };
  51
  52 /* Hash an inode map entry.  */
  53 static size_t
  54 ino_hash (void const *x, size_t table_size)
  55 {
  56   struct ino_map_ent const *p = x;
  57   ino_t ino = p->ino;
  58
  59   /* When INO is wider than size_t, exclusive-OR the words of INO into H.
  60      This avoids loss of info, without applying % to the wider type,
  61      which could be quite slow on some systems.  */
  62   size_t h = ino;
  63   unsigned int i;
  64   unsigned int n_words = sizeof ino / sizeof h + (sizeof ino % sizeof h != 0);
  65   for (i = 1; i < n_words; i++)
  66     h ^= ino >> CHAR_BIT * sizeof h * i;
  67
  68   return h % table_size;
  69 }
  70
  71 /* Return true if two inode map entries are the same.  */
  72 static bool
  73 ino_compare (void const *x, void const *y)
  74 {
  75   struct ino_map_ent const *a = x;
  76   struct ino_map_ent const *b = y;
  77   return a->ino == b->ino;
  78 }
  79
  80 /* Allocate an inode map that will hand out integers starting with
  81    NEXT_MAPPED_INO.  Return NULL if memory is exhausted.  */
  82 struct ino_map *
  83 ino_map_alloc (size_t next_mapped_ino)
  84 {
  85   struct ino_map *im = malloc (sizeof *im);
  86
  87   if (im)
  88     {
  89       enum { INITIAL_INO_MAP_TABLE_SIZE = 1021 };
  90       im->map = hash_initialize (INITIAL_INO_MAP_TABLE_SIZE, NULL,
  91                                  ino_hash, ino_compare, free);
  92       if (! im->map)
  93         {
  94           free (im);
  95           return NULL;
  96         }
  97       im->next_mapped_ino = next_mapped_ino;
  98       im->probe = NULL;
  99     }
 100
 101   return im;
 102 }
 103
 104 /* Free an inode map.  */
 105 void
 106 ino_map_free (struct ino_map *map)
 107 {
 108   hash_free (map->map);
 109   free (map->probe);
 110   free (map);
 111 }
 112
 113
 114 /* Insert into MAP the inode number INO if it's not there already,
 115    and return its nonnegative mapped inode number.
 116    If INO is already in MAP, return the existing mapped inode number.
 117    Return INO_MAP_INSERT_FAILURE on memory or counter exhaustion.  */
 118 size_t
 119 ino_map_insert (struct ino_map *im, ino_t ino)
 120 {
 121   struct ino_map_ent *ent;
 122
 123   /* Find space for the probe, reusing the cache if available.  */
 124   struct ino_map_ent *probe = im->probe;
 125   if (probe)
 126     {
 127       /* If repeating a recent query, return the cached result.   */
 128       if (probe->ino == ino)
 129         return probe->mapped_ino;
 130     }
 131   else
 132     {
 133       im->probe = probe = malloc (sizeof *probe);
 134       if (! probe)
 135         return INO_MAP_INSERT_FAILURE;
 136     }
 137
 138   probe->ino = ino;
 139   ent = hash_insert (im->map, probe);
 140   if (! ent)
 141     return INO_MAP_INSERT_FAILURE;
 142
 143   if (ent != probe)
 144     {
 145       /* Use the existing entry.  */
 146       probe->mapped_ino = ent->mapped_ino;
 147     }
 148   else
 149     {
 150       /* If adding 1 to map->next_mapped_ino would cause it to
 151          overflow to zero, then it must equal INO_MAP_INSERT_FAILURE,
 152          which is the value that should be returned in that case.
 153          Verify that this works.  */
 154       verify (INO_MAP_INSERT_FAILURE + 1 == 0);
 155
 156       /* Prepare to allocate a new probe next time; this one is in use.  */
 157       im->probe = NULL;
 158
 159       /* INO is new; allocate a mapped inode number for it.  */
 160       probe->mapped_ino = im->next_mapped_ino++;
 161     }
 162
 163   return probe->mapped_ino;
 164 }