1#include "cache.h" 2 3/* 4 * Returns the length (on a path component basis) of the longest 5 * common prefix match of 'name_a' and 'name_b'. 6 */ 7static int longest_path_match(const char *name_a, int len_a, 8 const char *name_b, int len_b, 9 int *previous_slash) 10{ 11 int max_len, match_len = 0, match_len_prev = 0, i = 0; 12 13 max_len = len_a < len_b ? len_a : len_b; 14 while (i < max_len && name_a[i] == name_b[i]) { 15 if (name_a[i] == '/') { 16 match_len_prev = match_len; 17 match_len = i; 18 } 19 i++; 20 } 21 /* 22 * Is 'name_b' a substring of 'name_a', the other way around, 23 * or is 'name_a' and 'name_b' the exact same string? 24 */ 25 if (i >= max_len && ((len_a > len_b && name_a[len_b] == '/') || 26 (len_a < len_b && name_b[len_a] == '/') || 27 (len_a == len_b))) { 28 match_len_prev = match_len; 29 match_len = i; 30 } 31 *previous_slash = match_len_prev; 32 return match_len; 33} 34 35static struct cache_def default_cache; 36 37static inline void reset_lstat_cache(struct cache_def *cache) 38{ 39 cache->path[0] = '\0'; 40 cache->len = 0; 41 cache->flags = 0; 42 /* 43 * The track_flags and prefix_len_stat_func members is only 44 * set by the safeguard rule inside lstat_cache() 45 */ 46} 47 48#define FL_DIR (1 << 0) 49#define FL_NOENT (1 << 1) 50#define FL_SYMLINK (1 << 2) 51#define FL_LSTATERR (1 << 3) 52#define FL_ERR (1 << 4) 53#define FL_FULLPATH (1 << 5) 54 55/* 56 * Check if name 'name' of length 'len' has a symlink leading 57 * component, or if the directory exists and is real, or not. 58 * 59 * To speed up the check, some information is allowed to be cached. 60 * This can be indicated by the 'track_flags' argument, which also can 61 * be used to indicate that we should check the full path. 62 * 63 * The 'prefix_len_stat_func' parameter can be used to set the length 64 * of the prefix, where the cache should use the stat() function 65 * instead of the lstat() function to test each path component. 66 */ 67static int lstat_cache(struct cache_def *cache, const char *name, int len, 68 int track_flags, int prefix_len_stat_func) 69{ 70 int match_len, last_slash, last_slash_dir, previous_slash; 71 int match_flags, ret_flags, save_flags, max_len, ret; 72 struct stat st; 73 74 if (cache->track_flags != track_flags || 75 cache->prefix_len_stat_func != prefix_len_stat_func) { 76 /* 77 * As a safeguard rule we clear the cache if the 78 * values of track_flags and/or prefix_len_stat_func 79 * does not match with the last supplied values. 80 */ 81 reset_lstat_cache(cache); 82 cache->track_flags = track_flags; 83 cache->prefix_len_stat_func = prefix_len_stat_func; 84 match_len = last_slash = 0; 85 } else { 86 /* 87 * Check to see if we have a match from the cache for 88 * the 2 "excluding" path types. 89 */ 90 match_len = last_slash = 91 longest_path_match(name, len, cache->path, cache->len, 92 &previous_slash); 93 match_flags = cache->flags & track_flags & (FL_NOENT|FL_SYMLINK); 94 95 if (!(track_flags & FL_FULLPATH) && match_len == len) 96 match_len = last_slash = previous_slash; 97 98 if (match_flags && match_len == cache->len) 99 return match_flags; 100 /* 101 * If we now have match_len > 0, we would know that 102 * the matched part will always be a directory. 103 * 104 * Also, if we are tracking directories and 'name' is 105 * a substring of the cache on a path component basis, 106 * we can return immediately. 107 */ 108 match_flags = track_flags & FL_DIR; 109 if (match_flags && len == match_len) 110 return match_flags; 111 } 112 113 /* 114 * Okay, no match from the cache so far, so now we have to 115 * check the rest of the path components. 116 */ 117 ret_flags = FL_DIR; 118 last_slash_dir = last_slash; 119 max_len = len < PATH_MAX ? len : PATH_MAX; 120 while (match_len < max_len) { 121 do { 122 cache->path[match_len] = name[match_len]; 123 match_len++; 124 } while (match_len < max_len && name[match_len] != '/'); 125 if (match_len >= max_len && !(track_flags & FL_FULLPATH)) 126 break; 127 last_slash = match_len; 128 cache->path[last_slash] = '\0'; 129 130 if (last_slash <= prefix_len_stat_func) 131 ret = stat(cache->path, &st); 132 else 133 ret = lstat(cache->path, &st); 134 135 if (ret) { 136 ret_flags = FL_LSTATERR; 137 if (errno == ENOENT) 138 ret_flags |= FL_NOENT; 139 } else if (S_ISDIR(st.st_mode)) { 140 last_slash_dir = last_slash; 141 continue; 142 } else if (S_ISLNK(st.st_mode)) { 143 ret_flags = FL_SYMLINK; 144 } else { 145 ret_flags = FL_ERR; 146 } 147 break; 148 } 149 150 /* 151 * At the end update the cache. Note that max 3 different 152 * path types, FL_NOENT, FL_SYMLINK and FL_DIR, can be cached 153 * for the moment! 154 */ 155 save_flags = ret_flags & track_flags & (FL_NOENT|FL_SYMLINK); 156 if (save_flags && last_slash > 0 && last_slash <= PATH_MAX) { 157 cache->path[last_slash] = '\0'; 158 cache->len = last_slash; 159 cache->flags = save_flags; 160 } else if ((track_flags & FL_DIR) && 161 last_slash_dir > 0 && last_slash_dir <= PATH_MAX) { 162 /* 163 * We have a separate test for the directory case, 164 * since it could be that we have found a symlink or a 165 * non-existing directory and the track_flags says 166 * that we cannot cache this fact, so the cache would 167 * then have been left empty in this case. 168 * 169 * But if we are allowed to track real directories, we 170 * can still cache the path components before the last 171 * one (the found symlink or non-existing component). 172 */ 173 cache->path[last_slash_dir] = '\0'; 174 cache->len = last_slash_dir; 175 cache->flags = FL_DIR; 176 } else { 177 reset_lstat_cache(cache); 178 } 179 return ret_flags; 180} 181 182#define USE_ONLY_LSTAT 0 183 184/* 185 * Return non-zero if path 'name' has a leading symlink component 186 */ 187int threaded_has_symlink_leading_path(struct cache_def *cache, const char *name, int len) 188{ 189 return lstat_cache(cache, name, len, FL_SYMLINK|FL_DIR, USE_ONLY_LSTAT) & FL_SYMLINK; 190} 191 192/* 193 * Return non-zero if path 'name' has a leading symlink component 194 */ 195int has_symlink_leading_path(const char *name, int len) 196{ 197 return threaded_has_symlink_leading_path(&default_cache, name, len); 198} 199 200/* 201 * Return non-zero if path 'name' has a leading symlink component or 202 * if some leading path component does not exists. 203 */ 204int has_symlink_or_noent_leading_path(const char *name, int len) 205{ 206 struct cache_def *cache = &default_cache; /* FIXME */ 207 return lstat_cache(cache, name, len, 208 FL_SYMLINK|FL_NOENT|FL_DIR, USE_ONLY_LSTAT) & 209 (FL_SYMLINK|FL_NOENT); 210} 211 212/* 213 * Return non-zero if all path components of 'name' exists as a 214 * directory. If prefix_len > 0, we will test with the stat() 215 * function instead of the lstat() function for a prefix length of 216 * 'prefix_len', thus we then allow for symlinks in the prefix part as 217 * long as those points to real existing directories. 218 */ 219int has_dirs_only_path(const char *name, int len, int prefix_len) 220{ 221 struct cache_def *cache = &default_cache; /* FIXME */ 222 return lstat_cache(cache, name, len, 223 FL_DIR|FL_FULLPATH, prefix_len) & 224 FL_DIR; 225} 226 227static struct removal_def { 228 char path[PATH_MAX]; 229 int len; 230} removal; 231 232static void do_remove_scheduled_dirs(int new_len) 233{ 234 while (removal.len > new_len) { 235 removal.path[removal.len] = '\0'; 236 if (rmdir(removal.path)) 237 break; 238 do { 239 removal.len--; 240 } while (removal.len > new_len && 241 removal.path[removal.len] != '/'); 242 } 243 removal.len = new_len; 244} 245 246void schedule_dir_for_removal(const char *name, int len) 247{ 248 int match_len, last_slash, i, previous_slash; 249 250 match_len = last_slash = i = 251 longest_path_match(name, len, removal.path, removal.len, 252 &previous_slash); 253 /* Find last slash inside 'name' */ 254 while (i < len) { 255 if (name[i] == '/') 256 last_slash = i; 257 i++; 258 } 259 260 /* 261 * If we are about to go down the directory tree, we check if 262 * we must first go upwards the tree, such that we then can 263 * remove possible empty directories as we go upwards. 264 */ 265 if (match_len < last_slash && match_len < removal.len) 266 do_remove_scheduled_dirs(match_len); 267 /* 268 * If we go deeper down the directory tree, we only need to 269 * save the new path components as we go down. 270 */ 271 if (match_len < last_slash) { 272 memcpy(&removal.path[match_len], &name[match_len], 273 last_slash - match_len); 274 removal.len = last_slash; 275 } 276} 277 278void remove_scheduled_dirs(void) 279{ 280 do_remove_scheduled_dirs(0); 281}