1/* Copyright libuv project contributors. All rights reserved. 2 * 3 * Permission is hereby granted, free of charge, to any person obtaining a copy 4 * of this software and associated documentation files (the "Software"), to 5 * deal in the Software without restriction, including without limitation the 6 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 7 * sell copies of the Software, and to permit persons to whom the Software is 8 * furnished to do so, subject to the following conditions: 9 * 10 * The above copyright notice and this permission notice shall be included in 11 * all copies or substantial portions of the Software. 12 * 13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 16 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 17 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 18 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 19 * IN THE SOFTWARE. 20 */ 21 22#ifndef UV_WIN_FS_FD_HASH_INL_H_ 23#define UV_WIN_FS_FD_HASH_INL_H_ 24 25#include "uv.h" 26#include "internal.h" 27 28/* Files are only inserted in uv__fd_hash when the UV_FS_O_FILEMAP flag is 29 * specified. Thus, when uv__fd_hash_get returns true, the file mapping in the 30 * info structure should be used for read/write operations. 31 * 32 * If the file is empty, the mapping field will be set to 33 * INVALID_HANDLE_VALUE. This is not an issue since the file mapping needs to 34 * be created anyway when the file size changes. 35 * 36 * Since file descriptors are sequential integers, the modulo operator is used 37 * as hashing function. For each bucket, a single linked list of arrays is 38 * kept to minimize allocations. A statically allocated memory buffer is kept 39 * for the first array in each bucket. */ 40 41 42#define UV__FD_HASH_SIZE 256 43#define UV__FD_HASH_GROUP_SIZE 16 44 45struct uv__fd_info_s { 46 int flags; 47 BOOLEAN is_directory; 48 HANDLE mapping; 49 LARGE_INTEGER size; 50 LARGE_INTEGER current_pos; 51}; 52 53struct uv__fd_hash_entry_s { 54 uv_file fd; 55 struct uv__fd_info_s info; 56}; 57 58struct uv__fd_hash_entry_group_s { 59 struct uv__fd_hash_entry_s entries[UV__FD_HASH_GROUP_SIZE]; 60 struct uv__fd_hash_entry_group_s* next; 61}; 62 63struct uv__fd_hash_bucket_s { 64 size_t size; 65 struct uv__fd_hash_entry_group_s* data; 66}; 67 68 69static uv_mutex_t uv__fd_hash_mutex; 70 71static struct uv__fd_hash_entry_group_s 72 uv__fd_hash_entry_initial[UV__FD_HASH_SIZE * UV__FD_HASH_GROUP_SIZE]; 73static struct uv__fd_hash_bucket_s uv__fd_hash[UV__FD_HASH_SIZE]; 74 75 76INLINE static void uv__fd_hash_init(void) { 77 size_t i; 78 int err; 79 80 err = uv_mutex_init(&uv__fd_hash_mutex); 81 if (err) { 82 uv_fatal_error(err, "uv_mutex_init"); 83 } 84 85 for (i = 0; i < ARRAY_SIZE(uv__fd_hash); ++i) { 86 uv__fd_hash[i].size = 0; 87 uv__fd_hash[i].data = 88 uv__fd_hash_entry_initial + i * UV__FD_HASH_GROUP_SIZE; 89 } 90} 91 92#define FIND_COMMON_VARIABLES \ 93 unsigned i; \ 94 unsigned bucket = fd % ARRAY_SIZE(uv__fd_hash); \ 95 struct uv__fd_hash_entry_s* entry_ptr = NULL; \ 96 struct uv__fd_hash_entry_group_s* group_ptr; \ 97 struct uv__fd_hash_bucket_s* bucket_ptr = &uv__fd_hash[bucket]; 98 99#define FIND_IN_GROUP_PTR(group_size) \ 100 do { \ 101 for (i = 0; i < group_size; ++i) { \ 102 if (group_ptr->entries[i].fd == fd) { \ 103 entry_ptr = &group_ptr->entries[i]; \ 104 break; \ 105 } \ 106 } \ 107 } while (0) 108 109#define FIND_IN_BUCKET_PTR() \ 110 do { \ 111 size_t first_group_size = bucket_ptr->size % UV__FD_HASH_GROUP_SIZE; \ 112 if (bucket_ptr->size != 0 && first_group_size == 0) \ 113 first_group_size = UV__FD_HASH_GROUP_SIZE; \ 114 group_ptr = bucket_ptr->data; \ 115 FIND_IN_GROUP_PTR(first_group_size); \ 116 for (group_ptr = group_ptr->next; \ 117 group_ptr != NULL && entry_ptr == NULL; \ 118 group_ptr = group_ptr->next) \ 119 FIND_IN_GROUP_PTR(UV__FD_HASH_GROUP_SIZE); \ 120 } while (0) 121 122INLINE static int uv__fd_hash_get(int fd, struct uv__fd_info_s* info) { 123 FIND_COMMON_VARIABLES 124 125 uv_mutex_lock(&uv__fd_hash_mutex); 126 127 FIND_IN_BUCKET_PTR(); 128 129 if (entry_ptr != NULL) { 130 *info = entry_ptr->info; 131 } 132 133 uv_mutex_unlock(&uv__fd_hash_mutex); 134 return entry_ptr != NULL; 135} 136 137INLINE static void uv__fd_hash_add(int fd, struct uv__fd_info_s* info) { 138 FIND_COMMON_VARIABLES 139 140 uv_mutex_lock(&uv__fd_hash_mutex); 141 142 FIND_IN_BUCKET_PTR(); 143 144 if (entry_ptr == NULL) { 145 i = bucket_ptr->size % UV__FD_HASH_GROUP_SIZE; 146 147 if (bucket_ptr->size != 0 && i == 0) { 148 struct uv__fd_hash_entry_group_s* new_group_ptr = 149 uv__malloc(sizeof(*new_group_ptr)); 150 if (new_group_ptr == NULL) { 151 uv_fatal_error(ERROR_OUTOFMEMORY, "uv__malloc"); 152 } 153 new_group_ptr->next = bucket_ptr->data; 154 bucket_ptr->data = new_group_ptr; 155 } 156 157 bucket_ptr->size += 1; 158 entry_ptr = &bucket_ptr->data->entries[i]; 159 entry_ptr->fd = fd; 160 } 161 162 entry_ptr->info = *info; 163 164 uv_mutex_unlock(&uv__fd_hash_mutex); 165} 166 167INLINE static int uv__fd_hash_remove(int fd, struct uv__fd_info_s* info) { 168 FIND_COMMON_VARIABLES 169 170 uv_mutex_lock(&uv__fd_hash_mutex); 171 172 FIND_IN_BUCKET_PTR(); 173 174 if (entry_ptr != NULL) { 175 *info = entry_ptr->info; 176 177 bucket_ptr->size -= 1; 178 179 i = bucket_ptr->size % UV__FD_HASH_GROUP_SIZE; 180 if (entry_ptr != &bucket_ptr->data->entries[i]) { 181 *entry_ptr = bucket_ptr->data->entries[i]; 182 } 183 184 if (bucket_ptr->size != 0 && 185 bucket_ptr->size % UV__FD_HASH_GROUP_SIZE == 0) { 186 struct uv__fd_hash_entry_group_s* old_group_ptr = bucket_ptr->data; 187 bucket_ptr->data = old_group_ptr->next; 188 uv__free(old_group_ptr); 189 } 190 } 191 192 uv_mutex_unlock(&uv__fd_hash_mutex); 193 return entry_ptr != NULL; 194} 195 196#undef FIND_COMMON_VARIABLES 197#undef FIND_IN_GROUP_PTR 198#undef FIND_IN_BUCKET_PTR 199 200#endif /* UV_WIN_FS_FD_HASH_INL_H_ */ 201