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