-/* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
- * vim:expandtab:shiftwidth=8:tabstop=8:
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil; -*-
+ * vim:expandtab:shiftwidth=4:tabstop=4:
*
* GPL HEADER START
*
* miscellaneous libcfs stuff
*/
#define DEBUG_SUBSYSTEM S_LNET
-#include <lnet/types.h>
+#include <libcfs/libcfs.h>
+#include <errno.h>
/*
- * Convert server error code to client format. Error codes are from
- * Linux errno.h, so for Linux client---identity.
+ * IDR support routines
+ *
+ * local global id <-> handle context
*/
-int convert_server_error(__u64 ecode)
+
+/* idr definitions */
+
+#define IDR_BITS 7
+#define IDR_FULL 0xffffffff
+#define IDR_SIZE (1 << IDR_BITS)
+#define IDR_MASK ((1 << IDR_BITS)-1)
+#define MAX_ID_SHIFT (sizeof(int)*8 - 1)
+#define MAX_ID_BIT (1U << MAX_ID_SHIFT)
+#define MAX_ID_MASK (MAX_ID_BIT - 1)
+#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS
+#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL
+
+#define idr_set_bit(bit, v) (v) |= (1<<(bit))
+#define idr_clear_bit(bit, v) (v) &= ~(1<<(bit))
+#define idr_test_bit(bit, v) ((v) & (1<<(bit)))
+
+struct idr_layer {
+ uint32_t bitmap;
+ struct idr_layer *ary[IDR_SIZE];
+ int count;
+};
+
+struct idr_context {
+ struct idr_layer *top;
+ struct idr_layer *id_free;
+ int layers;
+ int id_free_cnt;
+};
+
+
+/*
+ * id (fd) <-> pointer (HANDLE)
+ */
+
+/**********************************************************
+ private structures and routines for id implementation
+***********************************************************/
+
+static struct idr_layer *alloc_layer(struct idr_context *idp)
{
- return cfs_error_code((NTSTATUS)ecode);
+ struct idr_layer *p;
+
+ if (!(p = idp->id_free))
+ return NULL;
+ idp->id_free = p->ary[0];
+ idp->id_free_cnt--;
+ p->ary[0] = NULL;
+ return p;
+}
+
+static int find_next_idrbit(uint32_t bm, int maxid, int n)
+{
+ while (n<maxid && !idr_test_bit(n, bm)) n++;
+ return n;
+}
+
+static void free_layer(struct idr_context *idp, struct idr_layer *p)
+{
+ p->ary[0] = idp->id_free;
+ idp->id_free = p;
+ idp->id_free_cnt++;
+}
+
+static int idr_pre_get(struct idr_context *idp)
+{
+ while (idp->id_free_cnt < IDR_FREE_MAX) {
+ struct idr_layer *new;
+
+ new = cfs_alloc(sizeof(struct idr_layer), CFS_ALLOC_ZERO);
+ if(new == NULL)
+ return (0);
+ free_layer(idp, new);
+ }
+ return 1;
+}
+
+static int sub_alloc(struct idr_context *idp, void *ptr, int *starting_id)
+{
+ int n, m, sh;
+ struct idr_layer *p, *new;
+ struct idr_layer *pa[MAX_LEVEL];
+ int l, id;
+ uint32_t bm;
+
+ memset(pa, 0, sizeof(pa));
+
+ id = *starting_id;
+ p = idp->top;
+ l = idp->layers;
+ pa[l--] = NULL;
+ while (1) {
+ /*
+ * We run around this while until we reach the leaf node...
+ */
+ n = (id >> (IDR_BITS*l)) & IDR_MASK;
+ bm = ~p->bitmap;
+ m = find_next_idrbit(bm, IDR_SIZE, n);
+ if (m == IDR_SIZE) {
+ /* no space available go back to previous layer. */
+ l++;
+ id = (id | ((1 << (IDR_BITS*l))-1)) + 1;
+ if (!(p = pa[l])) {
+ *starting_id = id;
+ return -2;
+ }
+ continue;
+ }
+ if (m != n) {
+ sh = IDR_BITS*l;
+ id = ((id >> sh) ^ n ^ m) << sh;
+ }
+ if ((id >= MAX_ID_BIT) || (id < 0))
+ return -1;
+ if (l == 0)
+ break;
+ /*
+ * Create the layer below if it is missing.
+ */
+ if (!p->ary[m]) {
+ if (!(new = alloc_layer(idp)))
+ return -1;
+ p->ary[m] = new;
+ p->count++;
+ }
+ pa[l--] = p;
+ p = p->ary[m];
+ }
+ /*
+ * We have reached the leaf node, plant the
+ * users pointer and return the raw id.
+ */
+ p->ary[m] = (struct idr_layer *)ptr;
+ idr_set_bit(m, p->bitmap);
+ p->count++;
+ /*
+ * If this layer is full mark the bit in the layer above
+ * to show that this part of the radix tree is full.
+ * This may complete the layer above and require walking
+ * up the radix tree.
+ */
+ n = id;
+ while (p->bitmap == IDR_FULL) {
+ if (!(p = pa[++l]))
+ break;
+ n = n >> IDR_BITS;
+ idr_set_bit((n & IDR_MASK), p->bitmap);
+ }
+ return(id);
+}
+
+static int idr_get_new_above_int(struct idr_context *idp, void *ptr, int starting_id)
+{
+ struct idr_layer *p, *new;
+ int layers, v, id;
+
+ idr_pre_get(idp);
+
+ id = starting_id;
+build_up:
+ p = idp->top;
+ layers = idp->layers;
+ if (!p) {
+ if (!(p = alloc_layer(idp)))
+ return -1;
+ layers = 1;
+ }
+ /*
+ * Add a new layer to the top of the tree if the requested
+ * id is larger than the currently allocated space.
+ */
+ while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) {
+ layers++;
+ if (!p->count)
+ continue;
+ if (!(new = alloc_layer(idp))) {
+ /*
+ * The allocation failed. If we built part of
+ * the structure tear it down.
+ */
+ for (new = p; p && p != idp->top; new = p) {
+ p = p->ary[0];
+ new->ary[0] = NULL;
+ new->bitmap = new->count = 0;
+ free_layer(idp, new);
+ }
+ return -1;
+ }
+ new->ary[0] = p;
+ new->count = 1;
+ if (p->bitmap == IDR_FULL)
+ idr_set_bit(0, new->bitmap);
+ p = new;
+ }
+ idp->top = p;
+ idp->layers = layers;
+ v = sub_alloc(idp, ptr, &id);
+ if (v == -2)
+ goto build_up;
+ return(v);
+}
+
+static int sub_remove(struct idr_context *idp, int shift, int id)
+{
+ struct idr_layer *p = idp->top;
+ struct idr_layer **pa[MAX_LEVEL];
+ struct idr_layer ***paa = &pa[0];
+ int n;
+
+ *paa = NULL;
+ *++paa = &idp->top;
+
+ while ((shift > 0) && p) {
+ n = (id >> shift) & IDR_MASK;
+ idr_clear_bit(n, p->bitmap);
+ *++paa = &p->ary[n];
+ p = p->ary[n];
+ shift -= IDR_BITS;
+ }
+ n = id & IDR_MASK;
+ if (p != NULL && idr_test_bit(n, p->bitmap)) {
+ idr_clear_bit(n, p->bitmap);
+ p->ary[n] = NULL;
+ while(*paa && ! --((**paa)->count)){
+ free_layer(idp, **paa);
+ **paa-- = NULL;
+ }
+ if ( ! *paa )
+ idp->layers = 0;
+ return 0;
+ }
+ return -1;
+}
+
+static void *_idr_find(struct idr_context *idp, int id)
+{
+ int n;
+ struct idr_layer *p;
+
+ n = idp->layers * IDR_BITS;
+ p = idp->top;
+ /*
+ * This tests to see if bits outside the current tree are
+ * present. If so, tain't one of ours!
+ */
+ if ((id & ~(~0 << MAX_ID_SHIFT)) >> (n + IDR_BITS))
+ return NULL;
+
+ /* Mask off upper bits we don't use for the search. */
+ id &= MAX_ID_MASK;
+
+ while (n >= IDR_BITS && p) {
+ n -= IDR_BITS;
+ p = p->ary[(id >> n) & IDR_MASK];
+ }
+ return((void *)p);
+}
+
+static int _idr_remove(struct idr_context *idp, int id)
+{
+ struct idr_layer *p;
+
+ /* Mask off upper bits we don't use for the search. */
+ id &= MAX_ID_MASK;
+
+ if (sub_remove(idp, (idp->layers - 1) * IDR_BITS, id) == -1) {
+ return -1;
+ }
+
+ if ( idp->top && idp->top->count == 1 &&
+ (idp->layers > 1) &&
+ idp->top->ary[0]) {
+ /* We can drop a layer */
+ p = idp->top->ary[0];
+ idp->top->bitmap = idp->top->count = 0;
+ free_layer(idp, idp->top);
+ idp->top = p;
+ --idp->layers;
+ }
+ while (idp->id_free_cnt >= IDR_FREE_MAX) {
+ p = alloc_layer(idp);
+ cfs_free(p);
+ }
+ return 0;
+}
+
+/**********************************************************
+ publick interfaces of id vs handle conversion
+***********************************************************/
+
+/**
+ initialise a idr tree.
+ */
+struct idr_context *cfs_idr_init()
+{
+ struct idr_context * idp = NULL;
+ idp = cfs_alloc(sizeof(struct idr_context), 0);
+ if (idp) {
+ memset(idp, 0, sizeof(struct idr_context));
+ }
+
+ return idp;
+}
+
+/**
+ remove an id from the idr tree
+*/
+int cfs_idr_remove(struct idr_context *idp, int id)
+{
+ int ret;
+ ret = _idr_remove((struct idr_context *)idp, id);
+ if (ret != 0) {
+ CWARN("WARNING: attempt to remove unset id %d in idtree\n", id);
+ }
+ return ret;
+}
+
+/**
+ allocate the next available id, and assign 'ptr' into its slot.
+ you can retrieve later this pointer using idr_find()
+*/
+int cfs_idr_get_new(struct idr_context *idp, void *ptr)
+{
+ int ret = idr_get_new_above_int(idp, ptr, 0);
+ if (ret > MAX_ID_MASK) {
+ cfs_idr_remove(idp, ret);
+ return -1;
+ }
+ return ret;
+}
+
+/**
+ allocate a new id, giving the first available value greater than or
+ equal to the given starting id
+*/
+int cfs_idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id)
+{
+ int ret = idr_get_new_above_int(idp, ptr, starting_id);
+ if (ret > MAX_ID_MASK) {
+ cfs_idr_remove(idp, ret);
+ return -1;
+ }
+ return ret;
+}
+
+/**
+ find a pointer value previously set with idr_get_new given an id
+*/
+void *cfs_idr_find(struct idr_context *idp, int id)
+{
+ return _idr_find(idp, id);
+}
+
+/**
+ destroy a idr tree.
+ */
+void cfs_idr_exit(struct idr_context *idp)
+{
+ if (idp) {
+ cfs_free(idp);
+ }
}
/*
return 0;
}
-
int cfs_error_code(NTSTATUS Status)
{
switch (Status) {
case STATUS_PORT_UNREACHABLE:
return (-ECONNRESET);
+ case STATUS_INSUFFICIENT_RESOURCES:
+ return (-ENOMEM);
+
case STATUS_PAGEFILE_QUOTA:
case STATUS_NO_MEMORY:
case STATUS_CONFLICTING_ADDRESSES:
case STATUS_QUOTA_EXCEEDED:
case STATUS_TOO_MANY_PAGING_FILES:
- case STATUS_INSUFFICIENT_RESOURCES:
case STATUS_WORKING_SET_QUOTA:
case STATUS_COMMITMENT_LIMIT:
case STATUS_TOO_MANY_ADDRESSES:
case STATUS_INVALID_BUFFER_SIZE:
return (-EMSGSIZE);
+ case STATUS_ADDRESS_ALREADY_EXISTS:
+ return (-EADDRINUSE);
}
if (NT_SUCCESS(Status))
return (-EINVAL);
}
+/*
+ * Convert server error code to client format. Error codes are from
+ * Linux errno.h, so for Linux client---identity.
+ */
+int convert_server_error(__u64 ecode)
+{
+ return cfs_error_code((NTSTATUS)ecode);
+}
-void cfs_stack_trace_fill(struct cfs_stack_trace *trace)
+char * strsep(char **strp, const char *delim)
{
+ char *begin, *end;
+
+ begin = *strp;
+ if (begin == NULL) {
+ return NULL;
+ }
+
+ if (delim[0] == '\0' || delim[1] == '\0') {
+ char ch = delim[0];
+ if (ch == '\0') {
+ end = NULL;
+ } else {
+ if (*begin == ch) {
+ end = begin;
+ } else if (*begin == '\0') {
+ end = NULL;
+ } else {
+ end = strchr (begin + 1, ch);
+ }
+ }
+ } else {
+ end = strpbrk (begin, delim);
+ }
+
+ if (end) {
+ *end++ = '\0';
+ *strp = end;
+ } else {
+ *strp = NULL;
+ }
+
+ return begin;
}
-void *cfs_stack_trace_frame(struct cfs_stack_trace *trace, int frame_no)
+/*
+ * strnchr - Find a character in a length limited string
+ * @s: The string to be searched
+ * @count: The number of characters to be searched
+ * @c: The character to search for
+ */
+
+char *strnchr(const char *s, size_t count, int c)
{
+ for (; count-- && *s != '\0'; ++s)
+ if (*s == (char) c)
+ return (char *) s;
return NULL;
}
+
+__u64 strtoull(char *nptr, char **endptr,int base)
+{
+ char *s = nptr;
+ __u64 acc, cutoff;
+ int c, neg = 0, any, cutlim;
+
+ /*
+ * See strtol for comments as to the logic used.
+ */
+ do {
+ c = *s++;
+ } while (cfs_isspace(c));
+ if (c == '-') {
+ neg = 1;
+ c = *s++;
+ } else if (c == '+')
+ c = *s++;
+ if ((base == 0 || base == 16) &&
+ c == '0' && (*s == 'x' || *s == 'X')) {
+ c = s[1];
+ s += 2;
+ base = 16;
+ }
+ if (base == 0)
+ base = c == '0' ? 8 : 10;
+ cutoff = (__u64)ULONG_LONG_MAX / (__u64)base;
+ cutlim = (int)((__u64)ULONG_LONG_MAX % (__u64)base);
+ for (acc = 0, any = 0;; c = *s++) {
+ if (cfs_isdigit(c))
+ c -= '0';
+ else if (cfs_isalpha(c))
+ c -= cfs_isupper(c) ? 'A' - 10 : 'a' - 10;
+ else
+ break;
+ if (c >= base)
+ break;
+ if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim))
+ any = -1;
+ else {
+ any = 1;
+ acc *= base;
+ acc += c;
+ }
+ }
+ if (any < 0) {
+ acc = ULONG_LONG_MAX;
+ } else if (neg)
+ acc = 0 - acc;
+ if (endptr != 0)
+ *endptr = (char *) (any ? s - 1 : nptr);
+ return (acc);
+}
+
+#if __KERNEL__
+
+#define BASE 65521L /* largest prime smaller than 65536 */
+#define NMAX 5552
+/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
+
+#define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
+#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
+#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
+#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
+#define DO16(buf) DO8(buf,0); DO8(buf,8);
+
+/* ========================================================================= */
+/*
+ Update a running Adler-32 checksum with the bytes buf[0..len-1] and
+ return the updated checksum. If buf is NULL, this function returns
+ the required initial value for the checksum.
+ An Adler-32 checksum is almost as reliable as a CRC32 but can be computed
+ much faster. Usage example:
+
+ uLong adler = adler32(0L, NULL, 0);
+
+ while (read_buffer(buffer, length) != EOF) {
+ adler = adler32(adler, buffer, length);
+ }
+ if (adler != original_adler) error();
+*/
+
+ULONG zlib_adler32(ULONG adler,
+ const BYTE *buf,
+ UINT len)
+{
+ unsigned long s1 = adler & 0xffff;
+ unsigned long s2 = (adler >> 16) & 0xffff;
+ int k;
+
+ if (buf == NULL) return 1L;
+
+ while (len > 0) {
+ k = len < NMAX ? len : NMAX;
+ len -= k;
+ while (k >= 16) {
+ DO16(buf);
+ buf += 16;
+ k -= 16;
+ }
+ if (k != 0) do {
+ s1 += *buf++;
+ s2 += s1;
+ } while (--k);
+ s1 %= BASE;
+ s2 %= BASE;
+ }
+ return (s2 << 16) | s1;
+}
+
+#if !defined(NTDDI_VERSION) || NTDDI_VERSION < 0x06000000
+_CRTIMP size_t __cdecl strnlen(const char * _Str, size_t _MaxCount)
+{
+ size_t len = 0;
+ while(len < _MaxCount && _Str[len++]);
+ return len;
+}
+#endif
+
+int (__cdecl *_cfs_isalpha)(int);
+int (__cdecl *_cfs_isspace)(int);
+int (__cdecl *_cfs_isupper)(int);
+int (__cdecl *_cfs_isdigit)(int);
+int (__cdecl *_cfs_isxdigit)(int);
+
+int cfs_isalpha(int c)
+{
+ if (_cfs_isalpha) {
+ return _cfs_isalpha(c);
+ } else {
+ return ((c >= 'a' && c <= 'z') ||
+ (c >= 'A' && c <= 'Z'));
+ }
+}
+
+int cfs_isspace(int c)
+{
+ if (_cfs_isspace) {
+ return _cfs_isspace(c);
+ } else {
+ return ((c >= 0x09 && c <= 0x0d) ||
+ (c == 0x20));
+ }
+}
+
+int cfs_isupper(int c)
+{
+ if (_cfs_isupper) {
+ return _cfs_isupper(c);
+ } else {
+ return (c >= 'A' && c <= 'Z');
+ }
+}
+
+int cfs_isdigit(int c)
+{
+ if (_cfs_isdigit) {
+ return _cfs_isdigit(c);
+ } else {
+ return (c >= '0' && c <= '9');
+ }
+}
+
+int cfs_isxdigit(int c)
+{
+ if (_cfs_isxdigit) {
+ return _cfs_isxdigit(c);
+ } else {
+ return ((c >= '0' && c <= '9') ||
+ (c >= 'A' && c <= 'F') ||
+ (c >= 'a' && c <= 'F'));
+ }
+}
+
+void cfs_libc_init()
+{
+ UNICODE_STRING fn;
+ int i;
+
+ struct {WCHAR * name; PVOID * addr;} funcs[] = {
+ { L"isspace", (PVOID *)&_cfs_isspace},
+ { L"isalpha", (PVOID *)&_cfs_isalpha},
+ { L"isupper", (PVOID *)&_cfs_isupper},
+ { L"isdigit", (PVOID *)&_cfs_isdigit},
+ { L"isxdigit",(PVOID *)&_cfs_isxdigit},
+ { NULL, NULL },
+ };
+
+ for (i=0; funcs[i].name != NULL; i++) {
+ RtlInitUnicodeString(&fn, funcs[i].name);
+ *(funcs[i].addr) = MmGetSystemRoutineAddress(&fn);
+ }
+
+#if DBG
+ ASSERT(cfs_isspace(0x20) && cfs_isspace(0x09) &&
+ cfs_isspace(0x0a) && cfs_isspace(0x0d) &&
+ !cfs_isspace('a') && !cfs_isspace('0'));
+ ASSERT(cfs_isalpha('a') && cfs_isalpha('Z') &&
+ !cfs_isalpha('0') && !cfs_isalpha('='));
+ ASSERT(cfs_isupper('A') && cfs_isupper('Z') &&
+ !cfs_isupper('a') && !cfs_isupper('='));
+ ASSERT(cfs_isdigit('0') && cfs_isdigit('9') &&
+ !cfs_isdigit('a') && !cfs_isdigit('#'));
+ ASSERT(cfs_isxdigit('0') && cfs_isxdigit('9') &&
+ cfs_isxdigit('a') && cfs_isxdigit('A') &&
+ cfs_isxdigit('F') && cfs_isxdigit('f') &&
+ !cfs_isxdigit('G') && !cfs_isxdigit('z'));
+#endif
+}
+
+#else
+
+unsigned int libcfs_subsystem_debug = ~0;
+
+int cfs_isalpha(int c)
+{
+ return isalpha(c);
+}
+
+int cfs_isspace(int c)
+{
+ return isspace(c);
+}
+
+int cfs_isupper(int c)
+{
+ return isupper(c);
+}
+
+int cfs_isdigit(int c)
+{
+ return isdigit(c);
+}
+
+int cfs_isxdigit(int c)
+{
+ return isxdigit(c);
+}
+
+void cfs_libc_init()
+{
+}
+
+
+#endif