1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=4:tabstop=4:
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 only,
10 * as published by the Free Software Foundation.
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License version 2 for more details (a copy is included
16 * in the LICENSE file that accompanied this code).
18 * You should have received a copy of the GNU General Public License
19 * version 2 along with this program; If not, see
20 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
29 * Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
30 * Use is subject to license terms.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
39 * miscellaneous libcfs stuff
41 #define DEBUG_SUBSYSTEM S_LNET
42 #include <libcfs/libcfs.h>
46 * IDR support routines
48 * local global id <-> handle context
54 #define IDR_FULL 0xffffffff
55 #define IDR_SIZE (1 << IDR_BITS)
56 #define IDR_MASK ((1 << IDR_BITS)-1)
57 #define MAX_ID_SHIFT (sizeof(int)*8 - 1)
58 #define MAX_ID_BIT (1U << MAX_ID_SHIFT)
59 #define MAX_ID_MASK (MAX_ID_BIT - 1)
60 #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
61 #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
63 #define idr_set_bit(bit, v) (v) |= (1<<(bit))
64 #define idr_clear_bit(bit, v) (v) &= ~(1<<(bit))
65 #define idr_test_bit(bit, v) ((v) & (1<<(bit)))
69 struct idr_layer *ary[IDR_SIZE];
74 struct idr_layer *top;
75 struct idr_layer *id_free;
82 * id (fd) <-> pointer (HANDLE)
85 /**********************************************************
86 private structures and routines for id implementation
87 ***********************************************************/
89 static struct idr_layer *alloc_layer(struct idr_context *idp)
93 if (!(p = idp->id_free))
95 idp->id_free = p->ary[0];
101 static int find_next_idrbit(uint32_t bm, int maxid, int n)
103 while (n<maxid && !idr_test_bit(n, bm)) n++;
107 static void free_layer(struct idr_context *idp, struct idr_layer *p)
109 p->ary[0] = idp->id_free;
114 static int idr_pre_get(struct idr_context *idp)
116 while (idp->id_free_cnt < IDR_FREE_MAX) {
117 struct idr_layer *new;
119 new = cfs_alloc(sizeof(struct idr_layer), CFS_ALLOC_ZERO);
122 free_layer(idp, new);
127 static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
130 struct idr_layer *p, *new;
131 struct idr_layer *pa[MAX_LEVEL];
135 memset(pa, 0, sizeof(pa));
143 * We run around this while until we reach the leaf node...
145 n = (id >> (IDR_BITS*l)) & IDR_MASK;
147 m = find_next_idrbit(bm, IDR_SIZE, n);
149 /* no space available go back to previous layer. */
151 id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
160 id = ((id >> sh) ^ n ^ m) << sh;
162 if ((id >= MAX_ID_BIT) || (id < 0))
167 * Create the layer below if it is missing.
170 if (!(new = alloc_layer(idp)))
179 * We have reached the leaf node, plant the
180 * users pointer and return the raw id.
182 p->ary[m] = (struct idr_layer *)ptr;
183 idr_set_bit(m, p->bitmap);
186 * If this layer is full mark the bit in the layer above
187 * to show that this part of the radix tree is full.
188 * This may complete the layer above and require walking
192 while (p->bitmap == IDR_FULL) {
196 idr_set_bit((n & IDR_MASK), p->bitmap);
201 static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
203 struct idr_layer *p, *new;
211 layers = idp->layers;
213 if (!(p = alloc_layer(idp)))
218 * Add a new layer to the top of the tree if the requested
219 * id is larger than the currently allocated space.
221 while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
225 if (!(new = alloc_layer(idp))) {
227 * The allocation failed. If we built part of
228 * the structure tear it down.
230 for (new = p; p && p != idp->top; new = p) {
233 new->bitmap = new->count = 0;
234 free_layer(idp, new);
240 if (p->bitmap == IDR_FULL)
241 idr_set_bit(0, new->bitmap);
245 idp->layers = layers;
246 v = sub_alloc(idp, ptr, &id);
252 static int sub_remove(struct idr_context *idp, int shift, int id)
254 struct idr_layer *p = idp->top;
255 struct idr_layer **pa[MAX_LEVEL];
256 struct idr_layer ***paa = &pa[0];
262 while ((shift > 0) && p) {
263 n = (id >> shift) & IDR_MASK;
264 idr_clear_bit(n, p->bitmap);
270 if (p != NULL && idr_test_bit(n, p->bitmap)) {
271 idr_clear_bit(n, p->bitmap);
273 while(*paa && ! --((**paa)->count)){
274 free_layer(idp, **paa);
284 static void *_idr_find(struct idr_context *idp, int id)
289 n = idp->layers * IDR_BITS;
292 * This tests to see if bits outside the current tree are
293 * present. If so, tain't one of ours!
295 if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
298 /* Mask off upper bits we don't use for the search. */
301 while (n >= IDR_BITS && p) {
303 p = p->ary[(id >> n) & IDR_MASK];
308 static int _idr_remove(struct idr_context *idp, int id)
312 /* Mask off upper bits we don't use for the search. */
315 if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
319 if ( idp->top && idp->top->count == 1 &&
322 /* We can drop a layer */
323 p = idp->top->ary[0];
324 idp->top->bitmap = idp->top->count = 0;
325 free_layer(idp, idp->top);
329 while (idp->id_free_cnt >= IDR_FREE_MAX) {
330 p = alloc_layer(idp);
336 /**********************************************************
337 publick interfaces of id vs handle conversion
338 ***********************************************************/
341 initialise a idr tree.
343 struct idr_context *cfs_idr_init()
345 struct idr_context * idp = NULL;
346 idp = cfs_alloc(sizeof(struct idr_context), 0);
348 memset(idp, 0, sizeof(struct idr_context));
355 remove an id from the idr tree
357 int cfs_idr_remove(struct idr_context *idp, int id)
360 ret = _idr_remove((struct idr_context *)idp, id);
362 CWARN("WARNING: attempt to remove unset id %d in idtree\n", id);
368 allocate the next available id, and assign 'ptr' into its slot.
369 you can retrieve later this pointer using idr_find()
371 int cfs_idr_get_new(struct idr_context *idp, void *ptr)
373 int ret = idr_get_new_above_int(idp, ptr, 0);
374 if (ret > MAX_ID_MASK) {
375 cfs_idr_remove(idp, ret);
382 allocate a new id, giving the first available value greater than or
383 equal to the given starting id
385 int cfs_idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id)
387 int ret = idr_get_new_above_int(idp, ptr, starting_id);
388 if (ret > MAX_ID_MASK) {
389 cfs_idr_remove(idp, ret);
396 find a pointer value previously set with idr_get_new given an id
398 void *cfs_idr_find(struct idr_context *idp, int id)
400 return _idr_find(idp, id);
406 void cfs_idr_exit(struct idr_context *idp)
414 * convert <fcntl.h> flag from client to server.
416 * nt kernel uses several members to describe the open flags
417 * such as DesiredAccess/ShareAccess/CreateDisposition/CreateOptions
418 * so it's better to convert when using, not here.
421 int convert_client_oflag(int cflag, int *result)
427 int cfs_error_code(NTSTATUS Status)
431 case STATUS_ACCESS_DENIED:
434 case STATUS_ACCESS_VIOLATION:
437 case STATUS_BUFFER_TOO_SMALL:
440 case STATUS_INVALID_PARAMETER:
443 case STATUS_NOT_IMPLEMENTED:
444 case STATUS_NOT_SUPPORTED:
445 return (-EOPNOTSUPP);
447 case STATUS_INVALID_ADDRESS:
448 case STATUS_INVALID_ADDRESS_COMPONENT:
449 return (-EADDRNOTAVAIL);
451 case STATUS_NO_SUCH_DEVICE:
452 case STATUS_NO_SUCH_FILE:
453 case STATUS_OBJECT_NAME_NOT_FOUND:
454 case STATUS_OBJECT_PATH_NOT_FOUND:
455 case STATUS_NETWORK_BUSY:
456 case STATUS_INVALID_NETWORK_RESPONSE:
457 case STATUS_UNEXPECTED_NETWORK_ERROR:
460 case STATUS_BAD_NETWORK_PATH:
461 case STATUS_NETWORK_UNREACHABLE:
462 case STATUS_PROTOCOL_UNREACHABLE:
463 return (-ENETUNREACH);
465 case STATUS_LOCAL_DISCONNECT:
466 case STATUS_TRANSACTION_ABORTED:
467 case STATUS_CONNECTION_ABORTED:
468 return (-ECONNABORTED);
470 case STATUS_REMOTE_DISCONNECT:
471 case STATUS_LINK_FAILED:
472 case STATUS_CONNECTION_DISCONNECTED:
473 case STATUS_CONNECTION_RESET:
474 case STATUS_PORT_UNREACHABLE:
475 return (-ECONNRESET);
477 case STATUS_INSUFFICIENT_RESOURCES:
480 case STATUS_PAGEFILE_QUOTA:
481 case STATUS_NO_MEMORY:
482 case STATUS_CONFLICTING_ADDRESSES:
483 case STATUS_QUOTA_EXCEEDED:
484 case STATUS_TOO_MANY_PAGING_FILES:
485 case STATUS_WORKING_SET_QUOTA:
486 case STATUS_COMMITMENT_LIMIT:
487 case STATUS_TOO_MANY_ADDRESSES:
488 case STATUS_REMOTE_RESOURCES:
491 case STATUS_INVALID_CONNECTION:
494 case STATUS_PIPE_DISCONNECTED:
498 case STATUS_IO_TIMEOUT:
499 case STATUS_LINK_TIMEOUT:
502 case STATUS_REMOTE_NOT_LISTENING:
503 case STATUS_CONNECTION_REFUSED:
504 return (-ECONNREFUSED);
506 case STATUS_HOST_UNREACHABLE:
507 return (-EHOSTUNREACH);
510 case STATUS_DEVICE_NOT_READY:
513 case STATUS_CANCELLED:
514 case STATUS_REQUEST_ABORTED:
517 case STATUS_BUFFER_OVERFLOW:
518 case STATUS_INVALID_BUFFER_SIZE:
521 case STATUS_ADDRESS_ALREADY_EXISTS:
522 return (-EADDRINUSE);
525 if (NT_SUCCESS(Status))
532 * Convert server error code to client format. Error codes are from
533 * Linux errno.h, so for Linux client---identity.
535 int convert_server_error(__u64 ecode)
537 return cfs_error_code((NTSTATUS)ecode);
540 char * strsep(char **strp, const char *delim)
549 if (delim[0] == '\0' || delim[1] == '\0') {
556 } else if (*begin == '\0') {
559 end = strchr (begin + 1, ch);
563 end = strpbrk (begin, delim);
577 * strnchr - Find a character in a length limited string
578 * @s: The string to be searched
579 * @count: The number of characters to be searched
580 * @c: The character to search for
583 char *strnchr(const char *s, size_t count, int c)
585 for (; count-- && *s != '\0'; ++s)
591 __u64 strtoull(char *nptr, char **endptr,int base)
595 int c, neg = 0, any, cutlim;
598 * See strtol for comments as to the logic used.
602 } while (cfs_isspace(c));
608 if ((base == 0 || base == 16) &&
609 c == '0' && (*s == 'x' || *s == 'X')) {
615 base = c == '0' ? 8 : 10;
616 cutoff = (__u64)ULONG_LONG_MAX / (__u64)base;
617 cutlim = (int)((__u64)ULONG_LONG_MAX % (__u64)base);
618 for (acc = 0, any = 0;; c = *s++) {
621 else if (cfs_isalpha(c))
622 c -= cfs_isupper(c) ? 'A' - 10 : 'a' - 10;
627 if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim))
636 acc = ULONG_LONG_MAX;
640 *endptr = (char *) (any ? s - 1 : nptr);
646 #define BASE 65521L /* largest prime smaller than 65536 */
648 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
650 #define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
651 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
652 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
653 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
654 #define DO16(buf) DO8(buf,0); DO8(buf,8);
656 /* ========================================================================= */
658 Update a running Adler-32 checksum with the bytes buf[0..len-1] and
659 return the updated checksum. If buf is NULL, this function returns
660 the required initial value for the checksum.
661 An Adler-32 checksum is almost as reliable as a CRC32 but can be computed
662 much faster. Usage example:
664 uLong adler = adler32(0L, NULL, 0);
666 while (read_buffer(buffer, length) != EOF) {
667 adler = adler32(adler, buffer, length);
669 if (adler != original_adler) error();
672 ULONG zlib_adler32(ULONG adler,
676 unsigned long s1 = adler & 0xffff;
677 unsigned long s2 = (adler >> 16) & 0xffff;
680 if (buf == NULL) return 1L;
683 k = len < NMAX ? len : NMAX;
697 return (s2 << 16) | s1;
700 #if !defined(NTDDI_VERSION) || NTDDI_VERSION < 0x06000000
701 _CRTIMP size_t __cdecl strnlen(const char * _Str, size_t _MaxCount)
704 while(len < _MaxCount && _Str[len++]);
709 int (__cdecl *_cfs_isalpha)(int);
710 int (__cdecl *_cfs_isspace)(int);
711 int (__cdecl *_cfs_isupper)(int);
712 int (__cdecl *_cfs_isdigit)(int);
713 int (__cdecl *_cfs_isxdigit)(int);
715 int cfs_isalpha(int c)
718 return _cfs_isalpha(c);
720 return ((c >= 'a' && c <= 'z') ||
721 (c >= 'A' && c <= 'Z'));
725 int cfs_isspace(int c)
728 return _cfs_isspace(c);
730 return ((c >= 0x09 && c <= 0x0d) ||
735 int cfs_isupper(int c)
738 return _cfs_isupper(c);
740 return (c >= 'A' && c <= 'Z');
744 int cfs_isdigit(int c)
747 return _cfs_isdigit(c);
749 return (c >= '0' && c <= '9');
753 int cfs_isxdigit(int c)
756 return _cfs_isxdigit(c);
758 return ((c >= '0' && c <= '9') ||
759 (c >= 'A' && c <= 'F') ||
760 (c >= 'a' && c <= 'F'));
769 struct {WCHAR * name; PVOID * addr;} funcs[] = {
770 { L"isspace", (PVOID *)&_cfs_isspace},
771 { L"isalpha", (PVOID *)&_cfs_isalpha},
772 { L"isupper", (PVOID *)&_cfs_isupper},
773 { L"isdigit", (PVOID *)&_cfs_isdigit},
774 { L"isxdigit",(PVOID *)&_cfs_isxdigit},
778 for (i=0; funcs[i].name != NULL; i++) {
779 RtlInitUnicodeString(&fn, funcs[i].name);
780 *(funcs[i].addr) = MmGetSystemRoutineAddress(&fn);
784 ASSERT(cfs_isspace(0x20) && cfs_isspace(0x09) &&
785 cfs_isspace(0x0a) && cfs_isspace(0x0d) &&
786 !cfs_isspace('a') && !cfs_isspace('0'));
787 ASSERT(cfs_isalpha('a') && cfs_isalpha('Z') &&
788 !cfs_isalpha('0') && !cfs_isalpha('='));
789 ASSERT(cfs_isupper('A') && cfs_isupper('Z') &&
790 !cfs_isupper('a') && !cfs_isupper('='));
791 ASSERT(cfs_isdigit('0') && cfs_isdigit('9') &&
792 !cfs_isdigit('a') && !cfs_isdigit('#'));
793 ASSERT(cfs_isxdigit('0') && cfs_isxdigit('9') &&
794 cfs_isxdigit('a') && cfs_isxdigit('A') &&
795 cfs_isxdigit('F') && cfs_isxdigit('f') &&
796 !cfs_isxdigit('G') && !cfs_isxdigit('z'));
802 unsigned int libcfs_subsystem_debug = ~0;
804 int cfs_isalpha(int c)
809 int cfs_isspace(int c)
814 int cfs_isupper(int c)
819 int cfs_isdigit(int c)
824 int cfs_isxdigit(int c)