X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Futil.c;h=cbaffa73322e041bc9f2deff21f4957f0072d334;hb=e892d5ffb5749c0534fecd903e3e6a76819f1346;hp=e6d57dadfbef338fb5c2985bd3f7d7a58294889f;hpb=b53055f4da4f8de17c591ae07ddd782829d21cd8;p=sliver-openvswitch.git diff --git a/lib/util.c b/lib/util.c index e6d57dadf..cbaffa733 100644 --- a/lib/util.c +++ b/lib/util.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,7 +16,6 @@ #include #include "util.h" -#include #include #include #include @@ -24,17 +23,51 @@ #include #include #include +#include #include +#include "byte-order.h" #include "coverage.h" +#include "openvswitch/types.h" #include "vlog.h" VLOG_DEFINE_THIS_MODULE(util); COVERAGE_DEFINE(util_xalloc); +/* argv[0] without directory names. */ const char *program_name; + +/* Ordinarily "" but set to "monitor" for a monitor process or "worker" for a + * worker process. */ +const char *subprogram_name = ""; + +/* --version option output. */ static char *program_version; +void +ovs_assert_failure(const char *where, const char *function, + const char *condition) +{ + /* Prevent an infinite loop (or stack overflow) in case VLOG_ABORT happens + * to trigger an assertion failure of its own. */ + static int reentry = 0; + + switch (reentry++) { + case 0: + VLOG_ABORT("%s: assertion %s failed in %s()", + where, condition, function); + NOT_REACHED(); + + case 1: + fprintf(stderr, "%s: assertion %s failed in %s()", + where, condition, function); + abort(); + + default: + abort(); + } +} + void out_of_memory(void) { @@ -190,9 +223,14 @@ ovs_abort(int err_no, const char *format, ...) va_list args; va_start(args, format); - ovs_error_valist(err_no, format, args); - va_end(args); + ovs_abort_valist(err_no, format, args); +} +/* Same as ovs_abort() except that the arguments are supplied as a va_list. */ +void +ovs_abort_valist(int err_no, const char *format, va_list args) +{ + ovs_error_valist(err_no, format, args); abort(); } @@ -241,7 +279,12 @@ ovs_error_valist(int err_no, const char *format, va_list args) { int save_errno = errno; - fprintf(stderr, "%s: ", program_name); + if (subprogram_name[0]) { + fprintf(stderr, "%s(%s): ", program_name, subprogram_name); + } else { + fprintf(stderr, "%s: ", program_name); + } + vfprintf(stderr, format, args); if (err_no != 0) { fprintf(stderr, " (%s)", ovs_retval_to_string(err_no)); @@ -282,21 +325,35 @@ ovs_retval_to_string(int retval) * be called at the beginning of main() with "argv[0]" as the argument * to 'argv0'. * + * 'version' should contain the version of the caller's program. If 'version' + * is the same as the VERSION #define, the caller is assumed to be part of Open + * vSwitch. Otherwise, it is assumed to be an external program linking against + * the Open vSwitch libraries. + * * The 'date' and 'time' arguments should likely be called with * "__DATE__" and "__TIME__" to use the time the binary was built. * Alternatively, the "set_program_name" macro may be called to do this * automatically. */ void -set_program_name__(const char *argv0, const char *date, const char *time) +set_program_name__(const char *argv0, const char *version, const char *date, + const char *time) { const char *slash = strrchr(argv0, '/'); program_name = slash ? slash + 1 : argv0; free(program_version); - program_version = xasprintf("%s (Open vSwitch) "VERSION BUILDNR"\n" - "Compiled %s %s\n", - program_name, date, time); + + if (!strcmp(version, VERSION)) { + program_version = xasprintf("%s (Open vSwitch) "VERSION"\n" + "Compiled %s %s\n", + program_name, date, time); + } else { + program_version = xasprintf("%s %s\n" + "Open vSwitch Library "VERSION"\n" + "Compiled %s %s\n", + program_name, version, date, time); + } } /* Returns a pointer to a string describing the program version. The @@ -614,6 +671,90 @@ abs_file_name(const char *dir, const char *file_name) } } +/* Like readlink(), but returns the link name as a null-terminated string in + * allocated memory that the caller must eventually free (with free()). + * Returns NULL on error, in which case errno is set appropriately. */ +char * +xreadlink(const char *filename) +{ + size_t size; + + for (size = 64; ; size *= 2) { + char *buf = xmalloc(size); + ssize_t retval = readlink(filename, buf, size); + int error = errno; + + if (retval >= 0 && retval < size) { + buf[retval] = '\0'; + return buf; + } + + free(buf); + if (retval < 0) { + errno = error; + return NULL; + } + } +} + +/* Returns a version of 'filename' with symlinks in the final component + * dereferenced. This differs from realpath() in that: + * + * - 'filename' need not exist. + * + * - If 'filename' does exist as a symlink, its referent need not exist. + * + * - Only symlinks in the final component of 'filename' are dereferenced. + * + * The caller must eventually free the returned string (with free()). */ +char * +follow_symlinks(const char *filename) +{ + struct stat s; + char *fn; + int i; + + fn = xstrdup(filename); + for (i = 0; i < 10; i++) { + char *linkname; + char *next_fn; + + if (lstat(fn, &s) != 0 || !S_ISLNK(s.st_mode)) { + return fn; + } + + linkname = xreadlink(fn); + if (!linkname) { + VLOG_WARN("%s: readlink failed (%s)", filename, strerror(errno)); + return fn; + } + + if (linkname[0] == '/') { + /* Target of symlink is absolute so use it raw. */ + next_fn = linkname; + } else { + /* Target of symlink is relative so add to 'fn''s directory. */ + char *dir = dir_name(fn); + + if (!strcmp(dir, ".")) { + next_fn = linkname; + } else { + char *separator = dir[strlen(dir) - 1] == '/' ? "" : "/"; + next_fn = xasprintf("%s%s%s", dir, separator, linkname); + free(linkname); + } + + free(dir); + } + + free(fn); + fn = next_fn; + } + + VLOG_WARN("%s: too many levels of symlinks", filename); + free(fn); + return xstrdup(filename); +} /* Pass a value to this function if it is marked with * __attribute__((warn_unused_result)) and you genuinely want to ignore @@ -638,7 +779,7 @@ english_list_delimiter(size_t index, size_t total) int log_2_floor(uint32_t n) { - assert(n); + ovs_assert(n); #if !defined(UINT_MAX) || !defined(UINT32_MAX) #error "Someone screwed up the #includes." @@ -663,3 +804,371 @@ log_2_floor(uint32_t n) } #endif } + +/* Given a 32 bit word 'n', calculates ceil(log_2('n')). It is an error to + * call this function with 'n' == 0. */ +int +log_2_ceil(uint32_t n) +{ + return log_2_floor(n) + !is_pow2(n); +} + +/* Returns the number of trailing 0-bits in 'n'. Undefined if 'n' == 0. */ +#if !defined(UINT_MAX) || !defined(UINT32_MAX) +#error "Someone screwed up the #includes." +#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX +/* Defined inline in util.h. */ +#else +static int +raw_ctz(uint32_t n) +{ + unsigned int k; + int count = 31; + +#define CTZ_STEP(X) \ + k = n << (X); \ + if (k) { \ + count -= X; \ + n = k; \ + } + CTZ_STEP(16); + CTZ_STEP(8); + CTZ_STEP(4); + CTZ_STEP(2); + CTZ_STEP(1); +#undef CTZ_STEP + + return count; +} +#endif + +/* Returns the number of 1-bits in 'x', between 0 and 32 inclusive. */ +int +popcount(uint32_t x) +{ + /* In my testing, this implementation is over twice as fast as any other + * portable implementation that I tried, including GCC 4.4 + * __builtin_popcount(), although nonportable asm("popcnt") was over 50% + * faster. */ +#define INIT1(X) \ + ((((X) & (1 << 0)) != 0) + \ + (((X) & (1 << 1)) != 0) + \ + (((X) & (1 << 2)) != 0) + \ + (((X) & (1 << 3)) != 0) + \ + (((X) & (1 << 4)) != 0) + \ + (((X) & (1 << 5)) != 0) + \ + (((X) & (1 << 6)) != 0) + \ + (((X) & (1 << 7)) != 0)) +#define INIT2(X) INIT1(X), INIT1((X) + 1) +#define INIT4(X) INIT2(X), INIT2((X) + 2) +#define INIT8(X) INIT4(X), INIT4((X) + 4) +#define INIT16(X) INIT8(X), INIT8((X) + 8) +#define INIT32(X) INIT16(X), INIT16((X) + 16) +#define INIT64(X) INIT32(X), INIT32((X) + 32) + + static const uint8_t popcount8[256] = { + INIT64(0), INIT64(64), INIT64(128), INIT64(192) + }; + + return (popcount8[x & 0xff] + + popcount8[(x >> 8) & 0xff] + + popcount8[(x >> 16) & 0xff] + + popcount8[x >> 24]); +} + +/* Returns true if the 'n' bytes starting at 'p' are zeros. */ +bool +is_all_zeros(const uint8_t *p, size_t n) +{ + size_t i; + + for (i = 0; i < n; i++) { + if (p[i] != 0x00) { + return false; + } + } + return true; +} + +/* Returns true if the 'n' bytes starting at 'p' are 0xff. */ +bool +is_all_ones(const uint8_t *p, size_t n) +{ + size_t i; + + for (i = 0; i < n; i++) { + if (p[i] != 0xff) { + return false; + } + } + return true; +} + +/* Copies 'n_bits' bits starting from bit 'src_ofs' in 'src' to the 'n_bits' + * starting from bit 'dst_ofs' in 'dst'. 'src' is 'src_len' bytes long and + * 'dst' is 'dst_len' bytes long. + * + * If you consider all of 'src' to be a single unsigned integer in network byte + * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit + * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is + * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len - + * 2], and so on. Similarly for 'dst'. + * + * Required invariants: + * src_ofs + n_bits <= src_len * 8 + * dst_ofs + n_bits <= dst_len * 8 + * 'src' and 'dst' must not overlap. + */ +void +bitwise_copy(const void *src_, unsigned int src_len, unsigned int src_ofs, + void *dst_, unsigned int dst_len, unsigned int dst_ofs, + unsigned int n_bits) +{ + const uint8_t *src = src_; + uint8_t *dst = dst_; + + src += src_len - (src_ofs / 8 + 1); + src_ofs %= 8; + + dst += dst_len - (dst_ofs / 8 + 1); + dst_ofs %= 8; + + if (src_ofs == 0 && dst_ofs == 0) { + unsigned int n_bytes = n_bits / 8; + if (n_bytes) { + dst -= n_bytes - 1; + src -= n_bytes - 1; + memcpy(dst, src, n_bytes); + + n_bits %= 8; + src--; + dst--; + } + if (n_bits) { + uint8_t mask = (1 << n_bits) - 1; + *dst = (*dst & ~mask) | (*src & mask); + } + } else { + while (n_bits > 0) { + unsigned int max_copy = 8 - MAX(src_ofs, dst_ofs); + unsigned int chunk = MIN(n_bits, max_copy); + uint8_t mask = ((1 << chunk) - 1) << dst_ofs; + + *dst &= ~mask; + *dst |= ((*src >> src_ofs) << dst_ofs) & mask; + + src_ofs += chunk; + if (src_ofs == 8) { + src--; + src_ofs = 0; + } + dst_ofs += chunk; + if (dst_ofs == 8) { + dst--; + dst_ofs = 0; + } + n_bits -= chunk; + } + } +} + +/* Zeros the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'. 'dst' is + * 'dst_len' bytes long. + * + * If you consider all of 'dst' to be a single unsigned integer in network byte + * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit + * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is + * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len - + * 2], and so on. + * + * Required invariant: + * dst_ofs + n_bits <= dst_len * 8 + */ +void +bitwise_zero(void *dst_, unsigned int dst_len, unsigned dst_ofs, + unsigned int n_bits) +{ + uint8_t *dst = dst_; + + if (!n_bits) { + return; + } + + dst += dst_len - (dst_ofs / 8 + 1); + dst_ofs %= 8; + + if (dst_ofs) { + unsigned int chunk = MIN(n_bits, 8 - dst_ofs); + + *dst &= ~(((1 << chunk) - 1) << dst_ofs); + + n_bits -= chunk; + if (!n_bits) { + return; + } + + dst--; + } + + while (n_bits >= 8) { + *dst-- = 0; + n_bits -= 8; + } + + if (n_bits) { + *dst &= ~((1 << n_bits) - 1); + } +} + +/* Sets to 1 all of the 'n_bits' bits starting from bit 'dst_ofs' in 'dst'. + * 'dst' is 'dst_len' bytes long. + * + * If you consider all of 'dst' to be a single unsigned integer in network byte + * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit + * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is + * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len - + * 2], and so on. + * + * Required invariant: + * dst_ofs + n_bits <= dst_len * 8 + */ +void +bitwise_one(void *dst_, unsigned int dst_len, unsigned dst_ofs, + unsigned int n_bits) +{ + uint8_t *dst = dst_; + + if (!n_bits) { + return; + } + + dst += dst_len - (dst_ofs / 8 + 1); + dst_ofs %= 8; + + if (dst_ofs) { + unsigned int chunk = MIN(n_bits, 8 - dst_ofs); + + *dst |= ((1 << chunk) - 1) << dst_ofs; + + n_bits -= chunk; + if (!n_bits) { + return; + } + + dst--; + } + + while (n_bits >= 8) { + *dst-- = 0xff; + n_bits -= 8; + } + + if (n_bits) { + *dst |= (1 << n_bits) - 1; + } +} + +/* Scans the 'n_bits' bits starting from bit 'dst_ofs' in 'dst' for 1-bits. + * Returns false if any 1-bits are found, otherwise true. 'dst' is 'dst_len' + * bytes long. + * + * If you consider all of 'dst' to be a single unsigned integer in network byte + * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit + * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is + * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len - + * 2], and so on. + * + * Required invariant: + * dst_ofs + n_bits <= dst_len * 8 + */ +bool +bitwise_is_all_zeros(const void *p_, unsigned int len, unsigned int ofs, + unsigned int n_bits) +{ + const uint8_t *p = p_; + + if (!n_bits) { + return true; + } + + p += len - (ofs / 8 + 1); + ofs %= 8; + + if (ofs) { + unsigned int chunk = MIN(n_bits, 8 - ofs); + + if (*p & (((1 << chunk) - 1) << ofs)) { + return false; + } + + n_bits -= chunk; + if (!n_bits) { + return true; + } + + p--; + } + + while (n_bits >= 8) { + if (*p) { + return false; + } + n_bits -= 8; + p--; + } + + if (n_bits && *p & ((1 << n_bits) - 1)) { + return false; + } + + return true; +} + +/* Copies the 'n_bits' low-order bits of 'value' into the 'n_bits' bits + * starting at bit 'dst_ofs' in 'dst', which is 'dst_len' bytes long. + * + * If you consider all of 'dst' to be a single unsigned integer in network byte + * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit + * with value 1 in dst[dst_len - 1], bit 1 is the bit with value 2, bit 2 is + * the bit with value 4, ..., bit 8 is the bit with value 1 in dst[dst_len - + * 2], and so on. + * + * Required invariants: + * dst_ofs + n_bits <= dst_len * 8 + * n_bits <= 64 + */ +void +bitwise_put(uint64_t value, + void *dst, unsigned int dst_len, unsigned int dst_ofs, + unsigned int n_bits) +{ + ovs_be64 n_value = htonll(value); + bitwise_copy(&n_value, sizeof n_value, 0, + dst, dst_len, dst_ofs, + n_bits); +} + +/* Returns the value of the 'n_bits' bits starting at bit 'src_ofs' in 'src', + * which is 'src_len' bytes long. + * + * If you consider all of 'src' to be a single unsigned integer in network byte + * order, then bit N is the bit with value 2**N. That is, bit 0 is the bit + * with value 1 in src[src_len - 1], bit 1 is the bit with value 2, bit 2 is + * the bit with value 4, ..., bit 8 is the bit with value 1 in src[src_len - + * 2], and so on. + * + * Required invariants: + * src_ofs + n_bits <= src_len * 8 + * n_bits <= 64 + */ +uint64_t +bitwise_get(const void *src, unsigned int src_len, + unsigned int src_ofs, unsigned int n_bits) +{ + ovs_be64 value = htonll(0); + + bitwise_copy(src, src_len, src_ofs, + &value, sizeof value, 0, + n_bits); + return ntohll(value); +}