4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
27 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
37 * miscellaneous libcfs stuff
39 #define DEBUG_SUBSYSTEM S_LNET
40 #include <libcfs/libcfs.h>
44 * IDR support routines
46 * local global id <-> handle context
52 #define IDR_FULL 0xffffffff
53 #define IDR_SIZE (1 << IDR_BITS)
54 #define IDR_MASK ((1 << IDR_BITS)-1)
55 #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
56 #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
57 #define MAX_ID_MASK (MAX_ID_BIT - 1)
58 #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
59 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
61 #define idr_set_bit(bit, v) (v) |= (1<<(bit))
62 #define idr_clear_bit(bit, v) (v) &= ~(1<<(bit))
63 #define idr_test_bit(bit, v) ((v) & (1<<(bit)))
67 struct idr_layer *ary[IDR_SIZE];
72 struct idr_layer *top;
73 struct idr_layer *id_free;
80 * id (fd) <-> pointer (HANDLE)
83 /**********************************************************
84 private structures and routines for id implementation
85 ***********************************************************/
87 static struct idr_layer *alloc_layer(struct idr_context *idp)
91 if (!(p = idp->id_free))
93 idp->id_free = p->ary[0];
99 static int find_next_idrbit(uint32_t bm, int maxid, int n)
101 while (n<maxid && !idr_test_bit(n, bm)) n++;
105 static void free_layer(struct idr_context *idp, struct idr_layer *p)
107 p->ary[0] = idp->id_free;
112 static int idr_pre_get(struct idr_context *idp)
114 while (idp->id_free_cnt < IDR_FREE_MAX) {
115 struct idr_layer *new;
117 new = cfs_alloc(sizeof(struct idr_layer), CFS_ALLOC_ZERO);
120 free_layer(idp, new);
125 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
128 struct idr_layer *p, *new;
129 struct idr_layer *pa[MAX_LEVEL];
133 memset(pa, 0, sizeof(pa));
141 * We run around this while until we reach the leaf node...
143 n = (id >> (IDR_BITS*l)) & IDR_MASK;
145 m = find_next_idrbit(bm, IDR_SIZE, n);
147 /* no space available go back to previous layer. */
149 id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
158 id = ((id >> sh) ^ n ^ m) << sh;
160 if ((id >= MAX_ID_BIT) || (id < 0))
165 * Create the layer below if it is missing.
168 if (!(new = alloc_layer(idp)))
177 * We have reached the leaf node, plant the
178 * users pointer and return the raw id.
180 p->ary[m] = (struct idr_layer *)ptr;
181 idr_set_bit(m, p->bitmap);
184 * If this layer is full mark the bit in the layer above
185 * to show that this part of the radix tree is full.
186 * This may complete the layer above and require walking
190 while (p->bitmap == IDR_FULL) {
194 idr_set_bit((n & IDR_MASK), p->bitmap);
199 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
201 struct idr_layer *p, *new;
209 layers = idp->layers;
211 if (!(p = alloc_layer(idp)))
216 * Add a new layer to the top of the tree if the requested
217 * id is larger than the currently allocated space.
219 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
223 if (!(new = alloc_layer(idp))) {
225 * The allocation failed. If we built part of
226 * the structure tear it down.
228 for (new = p; p && p != idp->top; new = p) {
231 new->bitmap = new->count = 0;
232 free_layer(idp, new);
238 if (p->bitmap == IDR_FULL)
239 idr_set_bit(0, new->bitmap);
243 idp->layers = layers;
244 v = sub_alloc(idp, ptr, &id);
250 static int sub_remove(struct idr_context *idp, int shift, int id)
252 struct idr_layer *p = idp->top;
253 struct idr_layer **pa[MAX_LEVEL];
254 struct idr_layer ***paa = &pa[0];
260 while ((shift > 0) && p) {
261 n = (id >> shift) & IDR_MASK;
262 idr_clear_bit(n, p->bitmap);
268 if (p != NULL && idr_test_bit(n, p->bitmap)) {
269 idr_clear_bit(n, p->bitmap);
271 while(*paa && ! --((**paa)->count)){
272 free_layer(idp, **paa);
282 static void *_idr_find(struct idr_context *idp, int id)
287 n = idp->layers * IDR_BITS;
290 * This tests to see if bits outside the current tree are
291 * present. If so, tain't one of ours!
293 if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
296 /* Mask off upper bits we don't use for the search. */
299 while (n >= IDR_BITS && p) {
301 p = p->ary[(id >> n) & IDR_MASK];
306 static int _idr_remove(struct idr_context *idp, int id)
310 /* Mask off upper bits we don't use for the search. */
313 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
317 if ( idp->top && idp->top->count == 1 &&
320 /* We can drop a layer */
321 p = idp->top->ary[0];
322 idp->top->bitmap = idp->top->count = 0;
323 free_layer(idp, idp->top);
327 while (idp->id_free_cnt >= IDR_FREE_MAX) {
328 p = alloc_layer(idp);
334 /**********************************************************
335 publick interfaces of id vs handle conversion
336 ***********************************************************/
339 initialise a idr tree.
341 struct idr_context *cfs_idr_init()
343 struct idr_context * idp = NULL;
344 idp = cfs_alloc(sizeof(struct idr_context), 0);
346 memset(idp, 0, sizeof(struct idr_context));
353 remove an id from the idr tree
355 int cfs_idr_remove(struct idr_context *idp, int id)
358 ret = _idr_remove((struct idr_context *)idp, id);
360 CWARN("WARNING: attempt to remove unset id %d in idtree\n", id);
366 allocate the next available id, and assign 'ptr' into its slot.
367 you can retrieve later this pointer using idr_find()
369 int cfs_idr_get_new(struct idr_context *idp, void *ptr)
371 int ret = idr_get_new_above_int(idp, ptr, 0);
372 if (ret > MAX_ID_MASK) {
373 cfs_idr_remove(idp, ret);
380 allocate a new id, giving the first available value greater than or
381 equal to the given starting id
383 int cfs_idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id)
385 int ret = idr_get_new_above_int(idp, ptr, starting_id);
386 if (ret > MAX_ID_MASK) {
387 cfs_idr_remove(idp, ret);
394 find a pointer value previously set with idr_get_new given an id
396 void *cfs_idr_find(struct idr_context *idp, int id)
398 return _idr_find(idp, id);
404 void cfs_idr_exit(struct idr_context *idp)
412 * convert <fcntl.h> flag from client to server.
414 * nt kernel uses several members to describe the open flags
415 * such as DesiredAccess/ShareAccess/CreateDisposition/CreateOptions
416 * so it's better to convert when using, not here.
419 int convert_client_oflag(int cflag, int *result)
425 int cfs_error_code(NTSTATUS Status)
429 case STATUS_ACCESS_DENIED:
432 case STATUS_ACCESS_VIOLATION:
435 case STATUS_BUFFER_TOO_SMALL:
438 case STATUS_INVALID_PARAMETER:
441 case STATUS_NOT_IMPLEMENTED:
442 case STATUS_NOT_SUPPORTED:
443 return (-EOPNOTSUPP);
445 case STATUS_INVALID_ADDRESS:
446 case STATUS_INVALID_ADDRESS_COMPONENT:
447 return (-EADDRNOTAVAIL);
449 case STATUS_NO_SUCH_DEVICE:
450 case STATUS_NO_SUCH_FILE:
451 case STATUS_OBJECT_NAME_NOT_FOUND:
452 case STATUS_OBJECT_PATH_NOT_FOUND:
453 case STATUS_NETWORK_BUSY:
454 case STATUS_INVALID_NETWORK_RESPONSE:
455 case STATUS_UNEXPECTED_NETWORK_ERROR:
458 case STATUS_BAD_NETWORK_PATH:
459 case STATUS_NETWORK_UNREACHABLE:
460 case STATUS_PROTOCOL_UNREACHABLE:
461 return (-ENETUNREACH);
463 case STATUS_LOCAL_DISCONNECT:
464 case STATUS_TRANSACTION_ABORTED:
465 case STATUS_CONNECTION_ABORTED:
466 return (-ECONNABORTED);
468 case STATUS_REMOTE_DISCONNECT:
469 case STATUS_LINK_FAILED:
470 case STATUS_CONNECTION_DISCONNECTED:
471 case STATUS_CONNECTION_RESET:
472 case STATUS_PORT_UNREACHABLE:
473 return (-ECONNRESET);
475 case STATUS_INSUFFICIENT_RESOURCES:
478 case STATUS_PAGEFILE_QUOTA:
479 case STATUS_NO_MEMORY:
480 case STATUS_CONFLICTING_ADDRESSES:
481 case STATUS_QUOTA_EXCEEDED:
482 case STATUS_TOO_MANY_PAGING_FILES:
483 case STATUS_WORKING_SET_QUOTA:
484 case STATUS_COMMITMENT_LIMIT:
485 case STATUS_TOO_MANY_ADDRESSES:
486 case STATUS_REMOTE_RESOURCES:
489 case STATUS_INVALID_CONNECTION:
492 case STATUS_PIPE_DISCONNECTED:
496 case STATUS_IO_TIMEOUT:
497 case STATUS_LINK_TIMEOUT:
500 case STATUS_REMOTE_NOT_LISTENING:
501 case STATUS_CONNECTION_REFUSED:
502 return (-ECONNREFUSED);
504 case STATUS_HOST_UNREACHABLE:
505 return (-EHOSTUNREACH);
508 case STATUS_DEVICE_NOT_READY:
511 case STATUS_CANCELLED:
512 case STATUS_REQUEST_ABORTED:
515 case STATUS_BUFFER_OVERFLOW:
516 case STATUS_INVALID_BUFFER_SIZE:
519 case STATUS_ADDRESS_ALREADY_EXISTS:
520 return (-EADDRINUSE);
523 if (NT_SUCCESS(Status))
530 * Convert server error code to client format. Error codes are from
531 * Linux errno.h, so for Linux client---identity.
533 int convert_server_error(__u64 ecode)
535 return cfs_error_code((NTSTATUS)ecode);
538 char * strsep(char **strp, const char *delim)
547 if (delim[0] == '\0' || delim[1] == '\0') {
554 } else if (*begin == '\0') {
557 end = strchr (begin + 1, ch);
561 end = strpbrk (begin, delim);
575 * strnchr - Find a character in a length limited string
576 * @s: The string to be searched
577 * @count: The number of characters to be searched
578 * @c: The character to search for
581 char *strnchr(const char *s, size_t count, int c)
583 for (; count-- && *s != '\0'; ++s)
589 __u64 strtoull(char *nptr, char **endptr,int base)
593 int c, neg = 0, any, cutlim;
596 * See strtol for comments as to the logic used.
600 } while (cfs_isspace(c));
606 if ((base == 0 || base == 16) &&
607 c == '0' && (*s == 'x' || *s == 'X')) {
613 base = c == '0' ? 8 : 10;
614 cutoff = (__u64)ULONG_LONG_MAX / (__u64)base;
615 cutlim = (int)((__u64)ULONG_LONG_MAX % (__u64)base);
616 for (acc = 0, any = 0;; c = *s++) {
619 else if (cfs_isalpha(c))
620 c -= cfs_isupper(c) ? 'A' - 10 : 'a' - 10;
625 if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim))
634 acc = ULONG_LONG_MAX;
638 *endptr = (char *) (any ? s - 1 : nptr);
644 #define BASE 65521L /* largest prime smaller than 65536 */
646 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
648 #define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
649 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
650 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
651 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
652 #define DO16(buf) DO8(buf,0); DO8(buf,8);
654 /* ========================================================================= */
656 Update a running Adler-32 checksum with the bytes buf[0..len-1] and
657 return the updated checksum. If buf is NULL, this function returns
658 the required initial value for the checksum.
659 An Adler-32 checksum is almost as reliable as a CRC32 but can be computed
660 much faster. Usage example:
662 uLong adler = adler32(0L, NULL, 0);
664 while (read_buffer(buffer, length) != EOF) {
665 adler = adler32(adler, buffer, length);
667 if (adler != original_adler) error();
670 ULONG zlib_adler32(ULONG adler,
674 unsigned long s1 = adler & 0xffff;
675 unsigned long s2 = (adler >> 16) & 0xffff;
678 if (buf == NULL) return 1L;
681 k = len < NMAX ? len : NMAX;
695 return (s2 << 16) | s1;
698 #if !defined(NTDDI_VERSION) || NTDDI_VERSION < 0x06000000
699 _CRTIMP size_t __cdecl strnlen(const char * _Str, size_t _MaxCount)
702 while(len < _MaxCount && _Str[len++]);
707 int (__cdecl *_cfs_isalpha)(int);
708 int (__cdecl *_cfs_isspace)(int);
709 int (__cdecl *_cfs_isupper)(int);
710 int (__cdecl *_cfs_isdigit)(int);
711 int (__cdecl *_cfs_isxdigit)(int);
713 int cfs_isalpha(int c)
716 return _cfs_isalpha(c);
718 return ((c >= 'a' && c <= 'z') ||
719 (c >= 'A' && c <= 'Z'));
723 int cfs_isspace(int c)
726 return _cfs_isspace(c);
728 return ((c >= 0x09 && c <= 0x0d) ||
733 int cfs_isupper(int c)
736 return _cfs_isupper(c);
738 return (c >= 'A' && c <= 'Z');
742 int cfs_isdigit(int c)
745 return _cfs_isdigit(c);
747 return (c >= '0' && c <= '9');
751 int cfs_isxdigit(int c)
754 return _cfs_isxdigit(c);
756 return ((c >= '0' && c <= '9') ||
757 (c >= 'A' && c <= 'F') ||
758 (c >= 'a' && c <= 'F'));
767 struct {WCHAR * name; PVOID * addr;} funcs[] = {
768 { L"isspace", (PVOID *)&_cfs_isspace},
769 { L"isalpha", (PVOID *)&_cfs_isalpha},
770 { L"isupper", (PVOID *)&_cfs_isupper},
771 { L"isdigit", (PVOID *)&_cfs_isdigit},
772 { L"isxdigit",(PVOID *)&_cfs_isxdigit},
776 for (i=0; funcs[i].name != NULL; i++) {
777 RtlInitUnicodeString(&fn, funcs[i].name);
778 *(funcs[i].addr) = MmGetSystemRoutineAddress(&fn);
782 ASSERT(cfs_isspace(0x20) && cfs_isspace(0x09) &&
783 cfs_isspace(0x0a) && cfs_isspace(0x0d) &&
784 !cfs_isspace('a') && !cfs_isspace('0'));
785 ASSERT(cfs_isalpha('a') && cfs_isalpha('Z') &&
786 !cfs_isalpha('0') && !cfs_isalpha('='));
787 ASSERT(cfs_isupper('A') && cfs_isupper('Z') &&
788 !cfs_isupper('a') && !cfs_isupper('='));
789 ASSERT(cfs_isdigit('0') && cfs_isdigit('9') &&
790 !cfs_isdigit('a') && !cfs_isdigit('#'));
791 ASSERT(cfs_isxdigit('0') && cfs_isxdigit('9') &&
792 cfs_isxdigit('a') && cfs_isxdigit('A') &&
793 cfs_isxdigit('F') && cfs_isxdigit('f') &&
794 !cfs_isxdigit('G') && !cfs_isxdigit('z'));
800 unsigned int libcfs_subsystem_debug = ~0;
802 int cfs_isalpha(int c)
807 int cfs_isspace(int c)
812 int cfs_isupper(int c)
817 int cfs_isdigit(int c)
822 int cfs_isxdigit(int c)