contrib/libarchive-2/libarchive/archive_entry_link_resolver.c

   1 /*-
   2  * Copyright (c) 2003-2007 Tim Kientzle
   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(S) ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "archive_platform.h"
  27 __FBSDID("$FreeBSD$");
  28
  29 #ifdef HAVE_SYS_STAT_H
  30 #include <sys/stat.h>
  31 #endif
  32 #ifdef HAVE_ERRNO_H
  33 #include <errno.h>
  34 #endif
  35 #include <stdio.h>
  36 #ifdef HAVE_STDLIB_H
  37 #include <stdlib.h>
  38 #endif
  39 #ifdef HAVE_STRING_H
  40 #include <string.h>
  41 #endif
  42
  43 #include "archive_entry.h"
  44
  45 /* Initial size of link cache. */
  46 #define links_cache_initial_size 1024
  47
  48 struct archive_entry_linkresolver {
  49         char                     *last_name;
  50         unsigned long             number_entries;
  51         size_t                    number_buckets;
  52         struct links_entry      **buckets;
  53 };
  54
  55 struct links_entry {
  56         struct links_entry      *next;
  57         struct links_entry      *previous;
  58         int                      links;
  59         dev_t                    dev;
  60         ino_t                    ino;
  61         char                    *name;
  62 };
  63
  64 struct archive_entry_linkresolver *
  65 archive_entry_linkresolver_new(void)
  66 {
  67         struct archive_entry_linkresolver *links_cache;
  68         size_t i;
  69
  70         links_cache = malloc(sizeof(struct archive_entry_linkresolver));
  71         if (links_cache == NULL)
  72                 return (NULL);
  73         memset(links_cache, 0, sizeof(struct archive_entry_linkresolver));
  74         links_cache->number_buckets = links_cache_initial_size;
  75         links_cache->buckets = malloc(links_cache->number_buckets *
  76             sizeof(links_cache->buckets[0]));
  77         if (links_cache->buckets == NULL) {
  78                 free(links_cache);
  79                 return (NULL);
  80         }
  81         for (i = 0; i < links_cache->number_buckets; i++)
  82                 links_cache->buckets[i] = NULL;
  83         return (links_cache);
  84 }
  85
  86 void
  87 archive_entry_linkresolver_free(struct archive_entry_linkresolver *links_cache)
  88 {
  89         size_t i;
  90
  91         if (links_cache->buckets == NULL)
  92                 return;
  93
  94         for (i = 0; i < links_cache->number_buckets; i++) {
  95                 while (links_cache->buckets[i] != NULL) {
  96                         struct links_entry *lp = links_cache->buckets[i]->next;
  97                         if (links_cache->buckets[i]->name != NULL)
  98                                 free(links_cache->buckets[i]->name);
  99                         free(links_cache->buckets[i]);
 100                         links_cache->buckets[i] = lp;
 101                 }
 102         }
 103         free(links_cache->buckets);
 104         links_cache->buckets = NULL;
 105 }
 106
 107 const char *
 108 archive_entry_linkresolve(struct archive_entry_linkresolver *links_cache,
 109     struct archive_entry *entry)
 110 {
 111         struct links_entry      *le, **new_buckets;
 112         int                      hash;
 113         size_t                   i, new_size;
 114         dev_t                    dev;
 115         ino_t                    ino;
 116         int                      nlinks;
 117
 118
 119         /* Free a held name. */
 120         free(links_cache->last_name);
 121         links_cache->last_name = NULL;
 122
 123         /* If the links cache overflowed and got flushed, don't bother. */
 124         if (links_cache->buckets == NULL)
 125                 return (NULL);
 126
 127         dev = archive_entry_dev(entry);
 128         ino = archive_entry_ino(entry);
 129         nlinks = archive_entry_nlink(entry);
 130
 131         /* An entry with one link can't be a hard link. */
 132         if (nlinks == 1)
 133                 return (NULL);
 134
 135         /* If the links cache is getting too full, enlarge the hash table. */
 136         if (links_cache->number_entries > links_cache->number_buckets * 2)
 137         {
 138                 /* Try to enlarge the bucket list. */
 139                 new_size = links_cache->number_buckets * 2;
 140                 new_buckets = malloc(new_size * sizeof(struct links_entry *));
 141
 142                 if (new_buckets != NULL) {
 143                         memset(new_buckets, 0,
 144                             new_size * sizeof(struct links_entry *));
 145                         for (i = 0; i < links_cache->number_buckets; i++) {
 146                                 while (links_cache->buckets[i] != NULL) {
 147                                         /* Remove entry from old bucket. */
 148                                         le = links_cache->buckets[i];
 149                                         links_cache->buckets[i] = le->next;
 150
 151                                         /* Add entry to new bucket. */
 152                                         hash = (le->dev ^ le->ino) % new_size;
 153
 154                                         if (new_buckets[hash] != NULL)
 155                                                 new_buckets[hash]->previous =
 156                                                     le;
 157                                         le->next = new_buckets[hash];
 158                                         le->previous = NULL;
 159                                         new_buckets[hash] = le;
 160                                 }
 161                         }
 162                         free(links_cache->buckets);
 163                         links_cache->buckets = new_buckets;
 164                         links_cache->number_buckets = new_size;
 165                 }
 166         }
 167
 168         /* Try to locate this entry in the links cache. */
 169         hash = ( dev ^ ino ) % links_cache->number_buckets;
 170         for (le = links_cache->buckets[hash]; le != NULL; le = le->next) {
 171                 if (le->dev == dev && le->ino == ino) {
 172                         /*
 173                          * Decrement link count each time and release
 174                          * the entry if it hits zero.  This saves
 175                          * memory and is necessary for detecting
 176                          * missed links.
 177                          */
 178                         --le->links;
 179                         if (le->links > 0)
 180                                 return (le->name);
 181                         /*
 182                          * When we release the entry, save the name
 183                          * until the next call.
 184                          */
 185                         links_cache->last_name = le->name;
 186                         /*
 187                          * Release the entry.
 188                          */
 189                         if (le->previous != NULL)
 190                                 le->previous->next = le->next;
 191                         if (le->next != NULL)
 192                                 le->next->previous = le->previous;
 193                         if (links_cache->buckets[hash] == le)
 194                                 links_cache->buckets[hash] = le->next;
 195                         links_cache->number_entries--;
 196                         free(le);
 197                         return (links_cache->last_name);
 198                 }
 199         }
 200
 201         /* Add this entry to the links cache. */
 202         le = malloc(sizeof(struct links_entry));
 203         if (le == NULL)
 204                 return (NULL);
 205         le->name = strdup(archive_entry_pathname(entry));
 206         if (le->name == NULL) {
 207                 free(le);
 208                 return (NULL);
 209         }
 210
 211         /* If we could allocate the entry, record it. */
 212         if (links_cache->buckets[hash] != NULL)
 213                 links_cache->buckets[hash]->previous = le;
 214         links_cache->number_entries++;
 215         le->next = links_cache->buckets[hash];
 216         le->previous = NULL;
 217         links_cache->buckets[hash] = le;
 218         le->dev = dev;
 219         le->ino = ino;
 220         le->links = nlinks - 1;
 221         return (NULL);
 222 }