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