July 2010 - libdispatch-dev - lists.macosforge.org

Results from running libdispatch tests on Solaris using libkqueue and libdispatch with patches
by Joakim Johansson 30 Jul '10

30 Jul '10

Hi, If anyone is interested, the output of the working unit tests for libdispatch on Solaris 10 is attached below. This is done with libdispatch r188 + the patches posted to the list the last few days built together with libkqueue r271 together with a few patches posted on the libkqueue list. dispatch_priority seems to fail spuriously sometimes (even though it passed in the example below) and the starfish latency boundary test sometimes fails - this is on a Xeon 5500 box with 8 cores (of which 4 is HT). When running the test suite, a very large number of threads is created for some tests: 386 during dispatch_priority 35 during dispatch_priority2 257 during starfish It seems a bit excessive, what would be expected on such a configuration not having support for pthread_workqueue? I will try it using Mark Heily’s userspace pthread_workqueue implementation as well and see how that works. Joakim —— node5:~/gcd/trunk/testing> ./dispatch_api ================================================== [TEST] Dispatch (Public) API [PID] 16120 ================================================== Actual: 412850 Expected: 412850 [PASS] dispatch_get_main_queue node5:~/gcd/trunk/testing> ./dispatch_c99 ================================================== [TEST] Dispatch C99 [PID] 16135 ================================================== Actual: 412830 Expected: 412830 [PASS] dispatch_get_main_queue node5:~/gcd/trunk/testing> ./dispatch_cascade ================================================== [TEST] Dispatch Cascade [PID] 16150 ================================================== maxcount = 2464 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * ** * * * * * * * * * ** * * *** * * * * * node5:~/gcd/trunk/testing> ./dispatch_debug ================================================== [TEST] Dispatch Debug [PID] 16165 ================================================== node5:~/gcd/trunk/testing> ./dispatch_priority ================================================== [TEST] Dispatch Priority [PID] 16180 ================================================== LOW: 64 **************************************** DEFAULT: 60 ************************************** HIGH: 68 ******************************************* Actual: 192 Expected: 192 [PASS] blocks completed Actual: 64 Expected: <68 [PASS] high priority precedence node5:~/gcd/trunk/testing> ./dispatch_priority2 ================================================== [TEST] Dispatch Priority (Set Target Queue) [PID] 16195 ================================================== Actual: 413150 Expected: 413150 [PASS] q[i] Actual: 415a10 Expected: 415a10 [PASS] q[i] Actual: 415ac0 Expected: 415ac0 [PASS] q[i] LOW: 58 ************************************* DEFAULT: 67 ****************************************** HIGH: 67 ****************************************** Actual: 192 Expected: 192 [PASS] blocks completed Actual: 58 Expected: <67 [PASS] high priority precedence node5:~/gcd/trunk/testing> ./dispatch_starfish ================================================== [TEST] Dispatch Starfish [PID] 16210 ================================================== lap: 10 count: 1000 delta: 832448041 ns math: 415.808212 ns / lap Actual: 415 Expected: <1000 [PASS] Latency lap: 9 count: 1000 delta: 789866055 ns math: 394.538489 ns / lap Actual: 394 Expected: <1000 [PASS] Latency lap: 8 count: 1000 delta: 976664387 ns math: 487.844349 ns / lap Actual: 487 Expected: <1000 [PASS] Latency lap: 7 count: 1000 delta: 1625163520 ns math: 811.769990 ns / lap Actual: 811 Expected: <1000 [PASS] Latency lap: 6 count: 1000 delta: 1527922124 ns math: 763.197864 ns / lap Actual: 763 Expected: <1000 [PASS] Latency lap: 5 count: 1000 delta: 1293263436 ns math: 645.985732 ns / lap Actual: 645 Expected: <1000 [PASS] Latency lap: 4 count: 1000 delta: 1755776727 ns math: 877.011352 ns / lap Actual: 877 Expected: <1000 [PASS] Latency lap: 3 count: 1000 delta: 2045621497 ns math: 1021.788960 ns / lap Actual: 1021 Expected: <1000 [FAIL] Latency (dispatch_starfish.c:75) dispatch_starfish.c:75 lap: 2 count: 1000 delta: 997176198 ns math: 498.090009 ns / lap Actual: 498 Expected: <1000 [PASS] Latency lap: 1 count: 1000 delta: 1204968309 ns math: 601.882272 ns / lap Actual: 601 Expected: <1000 [PASS] Latency node5:~/gcd/trunk/testing> ./queue_finalizer ================================================== [TEST] Dispatch Queue Finalizer [PID] 16225 ================================================== Actual: 413390 Expected: 413390 [PASS] dispatch_queue_new Actual: 72f36169c7132463 Expected: 72f36169c7132463 [PASS] finalizer ran node5:~/gcd/trunk/testing>

2 3

PATCH - bugfix for dispatch_priority.c spurious failures where actual blocks completed != expected
by Joakim Johansson 28 Jul '10

28 Jul '10

I’ve had some problems with spurious failures of dispatch_priority/dispatch_priority2 tests on Solaris. It actually turned out to be a small bug in the test: ‘iterdone’ being size_t would wrap around rather than being negative (as it seems was assumed in the code). It could be fixed by changing the condition to look from the wraparound, or alternatively by consistently changing the use of size_t for the various ‘counts’ to use the long type instead. I’ve attached both flavors of the fix for consideration, both variants works fine now without spurious failures. Cheers, Joakim First patch variant checking for wraparound: --------------------------------- octo.tbricks.com:gcd/trunk/testing> svn diff dispatch_priority.c Index: dispatch_priority.c =================================================================== --- dispatch_priority.c (revision 188) +++ dispatch_priority.c (working copy) @@ -100,8 +100,8 @@ histogram(); test_stop(); exit(0); - } else if (iterdone > 0) { - __sync_add_and_fetch(count, 1); + } else if ((iterdone > 0) && (iterdone <= ITERATIONS)) { // We need to check that iterdone is not > ITERATIONS, as size_t is signed + __sync_add_and_fetch(count, 1); // 'iterations' wraps around and some thread may otherwise increase 'count' when the test is done } } ———————————————— Alternative patch changing the type from size_t to long ———————————————— octo.tbricks.com:gcd/trunk/testing> svn diff dispatch_priority.c Index: dispatch_priority.c =================================================================== --- dispatch_priority.c (revision 188) +++ dispatch_priority.c (working copy) @@ -48,21 +48,21 @@ int priorities[PRIORITIES] = { DISPATCH_QUEUE_PRIORITY_LOW, DISPATCH_QUEUE_PRIORITY_DEFAULT, DISPATCH_QUEUE_PRIORITY_HIGH }; union { - size_t count; + long count; char padding[64]; } counts[PRIORITIES]; -#define ITERATIONS (size_t)(PRIORITIES * BLOCKS * 0.50) -size_t iterations = ITERATIONS; +#define ITERATIONS (long)(PRIORITIES * BLOCKS * 0.50) +long iterations = ITERATIONS; void histogram(void) { - size_t maxcount = BLOCKS; - size_t sc[PRIORITIES]; + long maxcount = BLOCKS; + long sc[PRIORITIES]; - size_t total = 0; + long total = 0; - size_t x,y; + long x,y; for (y = 0; y < PRIORITIES; ++y) { sc[y] = counts[y].count; } @@ -86,10 +86,10 @@ void cpubusy(void* context) { - size_t *count = context; - size_t iterdone; + long *count = context; + long iterdone; - size_t idx; + long idx; for (idx = 0; idx < LOOP_COUNT; ++idx) { if (done) break; } octo.tbricks.com:gcd/trunk/testing>

1 0

Solaris portability - PATCH - m4/private-extern.m4
by Joakim Johansson 27 Jul '10

27 Jul '10

As mentioned, one final niggle was in the detection of the support for '__attribute__((visibility("hidden")))’. It turns out that this breaks on Solaris when you actually try to reference such a symbol with: -— conftest.c:56: warning: visibility attribute not supported in this configuration; ignored —— even though a compile with such declarations works just fine. The attached patch modifies the detection to not just compile such a symbol, but also to reference it through an assignment and enabling the treatment of warnings as errors. When tested, this yields the correct detection of support on both Darwin and Solaris (yes/no respectively). I believe this is the final patch needed to build libdispatch cleanly on Solaris using: ----- sh ./autogen.sh ./configure --disable-static gmake CFLAGS=-m64 —— (requires an installed version of libkqueue) Joakim ------------------------------------------- octo.tbricks.com:~/Network/gcd/trunk> svn diff m4/private-extern.m4 Index: m4/private-extern.m4 =================================================================== --- m4/private-extern.m4 (revision 188) +++ m4/private-extern.m4 (working copy) @@ -4,10 +4,12 @@ # AC_DEFUN([DISPATCH_C_PRIVATE_EXTERN], [ +AC_LANG_WERROR + AC_CACHE_CHECK([for __attribute__((visibility("hidden")))], dispatch_cv_hidden_visibility_attribute, [ - AC_TRY_LINK([], - [extern __attribute__ ((visibility ("hidden"))) int foo;], + AC_TRY_LINK([int foo; extern __attribute__ ((visibility ("hidden"))) int foo;], + [foo = 0;], [dispatch_cv_hidden_visibility_attribute=yes], [dispatch_cv_hidden_visibility_attribute=no])]) octo.tbricks.com:~/Network/gcd/trunk>

1 0

libdispatch now available in Debian GNU/Linux
by Mark Heily 27 Jul '10

27 Jul '10

I am pleased to announce that libdispatch is now included in the official Debian GNU/Linux package repository [1]. This package includes support for the "blocks" extension to C. I would like to express my gratitude to Julien Blache for sponsoring these packages, testing them, and providing great feedback and help improving the quality of the packages. I'd like to thank Robert Watson for accepting various patches to improve the portability of libdispatch. I will be submitting some more Linux-related patches in the near future. I would also like to thank the EGLIBC maintainers for accepting a patch to remove the uses of "__block" within <unistd.h> that conflict with the Blocks API. And finally, I want to thank Apple for releasing libdispatch as open source, and I hope that it is adopted as the foundation for writing software that can take full advantage of the multi-core and multi-processor systems that are becoming the norm. Cheers, - Mark [1] http://packages.debian.org/squeeze/libdispatch0 http://packages.debian.org/squeeze/libdispatch-dev

1 0

Solaris portability - PATCH - getprogname shim support
by Joakim Johansson 27 Jul '10

27 Jul '10

Falling back to retrieving program name for libdispatch debug file using getexecname() for Solaris. Also made the fallback getprogname function return a ‘const’ string to the program name to avoid warnings. Cheers, Joakim octo.tbricks.com:gcd/gcd/trunk> svn up At revision 188. octo.tbricks.com:gcd/gcd/trunk> svn diff Index: configure.ac =================================================================== --- configure.ac (revision 188) +++ configure.ac (working copy) @@ -193,7 +193,7 @@ AC_CHECK_DECLS([SIGEMT], [], [], [[#include <signal.h>]]) AC_CHECK_DECLS([VQ_UPDATE, VQ_VERYLOWDISK], [], [], [[#include <sys/mount.h>]]) AC_CHECK_DECLS([program_invocation_short_name], [], [], [[#include <errno.h>]]) -AC_CHECK_FUNCS([pthread_key_init_np pthread_main_np mach_absolute_time malloc_create_zone sysconf getprogname]) +AC_CHECK_FUNCS([pthread_key_init_np pthread_main_np mach_absolute_time malloc_create_zone sysconf getprogname getexecname]) AC_CHECK_DECLS([POSIX_SPAWN_START_SUSPENDED], [have_posix_spawn_start_suspended=true], Index: src/shims/getprogname.h =================================================================== --- src/shims/getprogname.h (revision 188) +++ src/shims/getprogname.h (working copy) @@ -23,15 +23,19 @@ #define __DISPATCH_SHIMS_GETPROGNAME__ #ifndef HAVE_GETPROGNAME -static inline char * + +static inline const char * getprogname(void) { # if HAVE_DECL_PROGRAM_INVOCATION_SHORT_NAME return program_invocation_short_name; +#elif HAVE_GETEXECNAME + return getexecname(); # else # error getprogname(3) is not available on this platform # endif } + #endif /* HAVE_GETPROGNAME */ #endif /* __DISPATCH_SHIMS_GETPROGNAME__ */ octo.tbricks.com:gcd/gcd/trunk>

3 4

Solaris portability - PATCH - fundamental libdispatch test suite patch
by Joakim Johansson 26 Jul '10

26 Jul '10

Hi, Attached is the patches required to be able to build the fundamental portable test suite of libdispatch on Solaris after the previous getprogname patch has been applied using libkqueue. The attached shim source files for arc4random/fgetln/asprintf were fundamentally based of previous open sources from opensource.apple.com - URL reference provided at the top of each. I hope it was stylistically ok to add the shims to libtest_la_SOURCES. With this, the following tests are operational (though not always successful…) on Solaris: ./dispatch_api ./dispatch_c99 ./dispatch_cascade ./dispatch_debug ./dispatch_priority ./dispatch_priority2 ./dispatch_starfish ./queue_finalizer Cheers, Joakim ————————————————————————————————————— octo.tbricks.com:~/Network/gcd/trunk> svn diff Index: configure.ac =================================================================== --- configure.ac (revision 188) +++ configure.ac (working copy) @@ -193,7 +193,7 @@ AC_CHECK_DECLS([SIGEMT], [], [], [[#include <signal.h>]]) AC_CHECK_DECLS([VQ_UPDATE, VQ_VERYLOWDISK], [], [], [[#include <sys/mount.h>]]) AC_CHECK_DECLS([program_invocation_short_name], [], [], [[#include <errno.h>]]) -AC_CHECK_FUNCS([pthread_key_init_np pthread_main_np mach_absolute_time malloc_create_zone sysconf getprogname]) +AC_CHECK_FUNCS([pthread_key_init_np pthread_main_np mach_absolute_time malloc_create_zone sysconf getprogname getexecname vasprintf asprintf arc4random fgetln]) AC_CHECK_DECLS([POSIX_SPAWN_START_SUSPENDED], [have_posix_spawn_start_suspended=true], Index: testing/shims/arc4random.h =================================================================== --- testing/shims/arc4random.h (revision 0) +++ testing/shims/arc4random.h (revision 0) @@ -0,0 +1,29 @@ +/* + * @APPLE_APACHE_LICENSE_HEADER_START@ + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * @APPLE_APACHE_LICENSE_HEADER_END@ + */ + + +#ifndef __DISPATCH_TESTS_SHIMS_ARC4RANDOM__ +#define __DISPATCH_TESTS_SHIMS_ARC4RANDOM__ + +#ifndef HAVE_ARC4RANDOM +unsigned int arc4random(); +#endif + +#endif /* __DISPATCH_TESTS_SHIMS_ARC4RANDOM__ */ + + Property changes on: testing/shims/arc4random.h ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/shims/fgetln.c =================================================================== --- testing/shims/fgetln.c (revision 0) +++ testing/shims/fgetln.c (revision 0) @@ -0,0 +1,93 @@ +/* $NetBSD: fgetln.c,v 1.3 2006/09/25 07:18:17 lukem Exp $ */ + +/*- + * libdispatch fgetln portability shim + * Based on http://www.opensource.apple.com/source/lukemftpd/lukemftpd-32/tnftpd/libnet… + * + * Copyright (c) 1998 The NetBSD Foundation, Inc. + * All rights reserved. + * + * This code is derived from software contributed to The NetBSD Foundation + * by Christos Zoulas. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of The NetBSD Foundation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config/config.h" + +#ifndef HAVE_FGETLN + +#include <stdio.h> +#include <stdlib.h> +#include <strings.h> +#include <errno.h> + +char * +fgetln(fp, len) + FILE *fp; + size_t *len; +{ + static char *buf = NULL; + static size_t bufsiz = 0; + char *ptr; + + + if (buf == NULL) { + bufsiz = BUFSIZ; + if ((buf = malloc(bufsiz)) == NULL) + return NULL; + } + + if (fgets(buf, bufsiz, fp) == NULL) + return NULL; + + *len = 0; + while ((ptr = strchr(&buf[*len], '\n')) == NULL) { + size_t nbufsiz = bufsiz + BUFSIZ; + char *nbuf = realloc(buf, nbufsiz); + + if (nbuf == NULL) { + int oerrno = errno; + free(buf); + errno = oerrno; + buf = NULL; + return NULL; + } else + buf = nbuf; + + *len = bufsiz; + if (fgets(&buf[bufsiz], BUFSIZ, fp) == NULL) + return buf; + + bufsiz = nbufsiz; + } + + *len = (ptr - buf) + 1; + return buf; +} + +#endif /* #ifndef HAVE_FGETLN */ + + Property changes on: testing/shims/fgetln.c ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/shims/fgetln.h =================================================================== --- testing/shims/fgetln.h (revision 0) +++ testing/shims/fgetln.h (revision 0) @@ -0,0 +1,29 @@ +/* + * @APPLE_APACHE_LICENSE_HEADER_START@ + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * @APPLE_APACHE_LICENSE_HEADER_END@ + */ + + +#ifndef __DISPATCH_TESTS_SHIMS_FGETLN__ +#define __DISPATCH_TESTS_SHIMS_FGETLN__ + +#ifndef HAVE_FGETLN +#include <stdio.h> + +char *fgetln(FILE *stream, size_t *len); +#endif + +#endif /* __DISPATCH_TESTS_SHIMS_FGETLN__ */ Property changes on: testing/shims/fgetln.h ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/shims/asprintf.c =================================================================== --- testing/shims/asprintf.c (revision 0) +++ testing/shims/asprintf.c (revision 0) @@ -0,0 +1,95 @@ +/* + * libdispatch asprintf portability shim, based on + * http://www.opensource.apple.com/source/OpenSSH/OpenSSH-142/openssh/openbsd-… + * + * + * Copyright (c) 2004 Darren Tucker. + * + * Based originally on asprintf.c from OpenBSD: + * Copyright (c) 1997 Todd C. Miller <Todd.Miller(a)courtesan.com> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "config/config.h" + +#ifndef HAVE_VASPRINTF + +#include <stdio.h> +#include <errno.h> +#include <stdarg.h> +#include <stdlib.h> +#include <sys/types.h> + +#define INIT_SZ 128 + +int +vasprintf(char **str, const char *fmt, va_list ap) +{ + int ret = -1; + va_list ap2; + char *string, *newstr; + size_t len; + + va_copy(ap2, ap); + if ((string = malloc(INIT_SZ)) == NULL) + goto fail; + + ret = vsnprintf(string, INIT_SZ, fmt, ap2); + if (ret >= 0 && ret < INIT_SZ) { /* succeeded with initial alloc */ + *str = string; + } else if (ret < 0) { /* Bad length */ + free(string); + goto fail; + } else { /* bigger than initial, realloc allowing for nul */ + len = (size_t)ret + 1; + if ((newstr = realloc(string, len)) == NULL) { + free(string); + goto fail; + } else { + va_end(ap2); + va_copy(ap2, ap); + ret = vsnprintf(newstr, len, fmt, ap2); + if (ret >= 0 && (size_t)ret < len) { + *str = newstr; + } else { /* failed with realloc'ed string, give up */ + free(newstr); + goto fail; + } + } + } + va_end(ap2); + return (ret); + +fail: + *str = NULL; + errno = ENOMEM; + va_end(ap2); + return (-1); +} +#endif + +#ifndef HAVE_ASPRINTF +int asprintf(char **str, const char *fmt, ...) +{ + va_list ap; + int ret; + + *str = NULL; + va_start(ap, fmt); + ret = vasprintf(str, fmt, ap); + va_end(ap); + + return ret; +} +#endif Property changes on: testing/shims/asprintf.c ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/shims/._arc4random.c =================================================================== Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Property changes on: testing/shims/._arc4random.c ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:mime-type + application/octet-stream Added: svn:owner + yes Added: svn:group + yes Index: testing/shims/arc4random.c =================================================================== --- testing/shims/arc4random.c (revision 0) +++ testing/shims/arc4random.c (revision 0) @@ -0,0 +1,241 @@ +/* + * arc4random() for libdispatch + * + * Based on http://www.opensource.apple.com/source/Libc/Libc-594.9.1/gen/FreeBSD/arc4ra… + * + * + * Arc4 random number generator for OpenBSD. + * Copyright 1996 David Mazieres <dm(a)lcs.mit.edu>. + * + * Modification and redistribution in source and binary forms is + * permitted provided that due credit is given to the author and the + * OpenBSD project (for instance by leaving this copyright notice + * intact). + */ + +/* + * This code is derived from section 17.1 of Applied Cryptography, + * second edition, which describes a stream cipher allegedly + * compatible with RSA Labs "RC4" cipher (the actual description of + * which is a trade secret). The same algorithm is used as a stream + * cipher called "arcfour" in Tatu Ylonen's ssh package. + * + * Here the stream cipher has been modified always to include the time + * when initializing the state. That makes it impossible to + * regenerate the same random sequence twice, so this can't be used + * for encryption, but will generate good random numbers. + * + * RC4 is a registered trademark of RSA Laboratories. + */ + +#include "config/config.h" + +#ifndef HAVE_ARC4RANDOM + +#include <sys/types.h> +#include <sys/time.h> +#include <stdlib.h> +#include <fcntl.h> +#include <unistd.h> +#include <pthread.h> + +struct arc4_stream { + uint8_t i; + uint8_t j; + uint8_t s[256]; +}; + +static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; + +#define __isthreaded 1 +#define RANDOMDEV "/dev/urandom" +#define THREAD_LOCK() \ + do { \ + if (__isthreaded) \ + pthread_mutex_lock(&arc4random_mtx); \ + } while (0) + +#define THREAD_UNLOCK() \ + do { \ + if (__isthreaded) \ + pthread_mutex_unlock(&arc4random_mtx); \ + } while (0) + +static struct arc4_stream rs; +static int rs_initialized; +static int rs_stired; + +static inline uint8_t arc4_getbyte(struct arc4_stream *); +static void arc4_stir(struct arc4_stream *); + +static inline void +arc4_init(as) + struct arc4_stream *as; +{ + int n; + + for (n = 0; n < 256; n++) + as->s[n] = n; + as->i = 0; + as->j = 0; +} + +static inline void +arc4_addrandom(as, dat, datlen) + struct arc4_stream *as; + u_char *dat; + int datlen; +{ + int n; + uint8_t si; + + as->i--; + for (n = 0; n < 256; n++) { + as->i = (as->i + 1); + si = as->s[as->i]; + as->j = (as->j + si + dat[n % datlen]); + as->s[as->i] = as->s[as->j]; + as->s[as->j] = si; + } +} + +static void +arc4_stir(as) + struct arc4_stream *as; +{ + int fd, n; + struct { + struct timeval tv; + pid_t pid; + uint8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)]; + } rdat; + + gettimeofday(&rdat.tv, NULL); + rdat.pid = getpid(); + fd = open(RANDOMDEV, O_RDONLY, 0); + if (fd >= 0) { + (void) read(fd, rdat.rnd, sizeof(rdat.rnd)); + close(fd); + } + /* fd < 0? Ah, what the heck. We'll just take whatever was on the + * stack... */ + + arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); + + /* + * Throw away the first N bytes of output, as suggested in the + * paper "Weaknesses in the Key Scheduling Algorithm of RC4" + * by Fluher, Mantin, and Shamir. N=1024 is based on + * suggestions in the paper "(Not So) Random Shuffles of RC4" + * by Ilya Mironov. + */ + for (n = 0; n < 1024; n++) + arc4_getbyte(as); +} + +static inline uint8_t +arc4_getbyte(as) + struct arc4_stream *as; +{ + uint8_t si, sj; + + as->i = (as->i + 1); + si = as->s[as->i]; + as->j = (as->j + si); + sj = as->s[as->j]; + as->s[as->i] = sj; + as->s[as->j] = si; + + return (as->s[(si + sj) & 0xff]); +} + +static inline uint32_t +arc4_getword(as) + struct arc4_stream *as; +{ + uint32_t val; + + val = arc4_getbyte(as) << 24; + val |= arc4_getbyte(as) << 16; + val |= arc4_getbyte(as) << 8; + val |= arc4_getbyte(as); + + return (val); +} + +static void +arc4_check_init(void) +{ + if (!rs_initialized) { + arc4_init(&rs); + rs_initialized = 1; + } +} + +static void +arc4_check_stir(void) +{ + if (!rs_stired) { + arc4_stir(&rs); + rs_stired = 1; + } +} + +void +arc4random_stir() +{ + THREAD_LOCK(); + arc4_check_init(); + arc4_stir(&rs); + THREAD_UNLOCK(); +} + +void +arc4random_addrandom(dat, datlen) + u_char *dat; + int datlen; +{ + THREAD_LOCK(); + arc4_check_init(); + arc4_check_stir(); + arc4_addrandom(&rs, dat, datlen); + THREAD_UNLOCK(); +} + +uint32_t +arc4random() +{ + uint32_t rnd; + + THREAD_LOCK(); + arc4_check_init(); + arc4_check_stir(); + rnd = arc4_getword(&rs); + THREAD_UNLOCK(); + + return (rnd); +} + +#if 0 +/*-------- Test code for i386 --------*/ +#include <stdio.h> +#include <machine/pctr.h> +int +main(int argc, char **argv) +{ + const int iter = 1000000; + int i; + pctrval v; + + v = rdtsc(); + for (i = 0; i < iter; i++) + arc4random(); + v = rdtsc() - v; + v /= iter; + + printf("%qd cycles\n", v); +} +#endif + +#endif /* HAVE_ARC4RANDOM */ + Property changes on: testing/shims/arc4random.c ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/shims/asprintf.h =================================================================== --- testing/shims/asprintf.h (revision 0) +++ testing/shims/asprintf.h (revision 0) @@ -0,0 +1,27 @@ +/* + * @APPLE_APACHE_LICENSE_HEADER_START@ + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * @APPLE_APACHE_LICENSE_HEADER_END@ + */ + + +#ifndef __DISPATCH_TESTS_SHIMS_ASPRINTF__ +#define __DISPATCH_TESTS_SHIMS_ASPRINTF__ + +#ifndef HAVE_ASPRINTF +int asprintf(char **str, const char *fmt, ...); +#endif + +#endif /* __DISPATCH_TESTS_SHIMS_ASPRINTF__ */ Property changes on: testing/shims/asprintf.h ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/dispatch_test.h =================================================================== --- testing/dispatch_test.h (revision 188) +++ testing/dispatch_test.h (working copy) @@ -1,6 +1,8 @@ #include <errno.h> +#include "os_shims.h" +#include <dispatch/dispatch.h> -__BEGIN_DECLS +__DISPATCH_BEGIN_DECLS void test_start(const char* desc); void test_stop(void); @@ -30,4 +32,5 @@ void _test_errno(const char* file, long line, const char* desc, long actual, long expected); #define test_errno(a,b,c) _test_errno(__FILE__, __LINE__, a, b, c) -__END_DECLS +__DISPATCH_END_DECLS + Index: testing/os_shims.h =================================================================== --- testing/os_shims.h (revision 0) +++ testing/os_shims.h (revision 0) @@ -0,0 +1,30 @@ +/* + * @APPLE_APACHE_LICENSE_HEADER_START@ + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + * @APPLE_APACHE_LICENSE_HEADER_END@ + */ + + +#ifndef __DISPATCH_TESTS_OS_SHIMS__ +#define __DISPATCH_TESTS_OS_SHIMS__ + +#include "config/config.h" + +#include "shims/asprintf.h" +#include "shims/arc4random.h" +#include "shims/fgetln.h" + +#endif /* __DISPATCH_TESTS_OS_SHIMS__ */ + Property changes on: testing/os_shims.h ___________________________________________________________________ Added: svn:unix-mode + yes Added: svn:owner + yes Added: svn:group + yes Added: svn:eol-style + native Index: testing/summarize.c =================================================================== --- testing/summarize.c (revision 188) +++ testing/summarize.c (working copy) @@ -18,7 +18,7 @@ * @APPLE_APACHE_LICENSE_HEADER_END@ */ -#include "config/config.h" +#include "os_shims.h" #include <stdio.h> #include <stdlib.h> Index: testing/Makefile.am =================================================================== --- testing/Makefile.am (revision 188) +++ testing/Makefile.am (working copy) @@ -5,7 +5,10 @@ noinst_LTLIBRARIES=libtest.la libtest_la_SOURCES= \ - dispatch_test.c + dispatch_test.c \ + shims/asprintf.c \ + shims/arc4random.c \ + shims/fgetln.c TESTS= \ dispatch_api \ octo.tbricks.com:~/Network/gcd/trunk> —————————————————————————————————————

1 0

Compiling libdispatch on mac os x 10.6
by Mirko Viviani 26 Jul '10

26 Jul '10

Hi, I'm trying to get a working version of libdispatch on macosx 10.6 to use its semaphores implementation on osx < 10.6. Compiled with xcode/gcc 4.2.1 (Apple Inc. build 5664)/10.6 SDK and apple semaphore optimizations. Unfortunately when I run the dispatch_sema.c test it fails: Starting program: /Users/Accounts/mirko/src/libdispatch/testing/a.out Reading symbols for shared libraries +. done ================================================== [TEST] Dispatch Semaphore [PID] 22816 ================================================== Program received signal EXC_BAD_INSTRUCTION, Illegal instruction/operand. [Switching to process 22816] 0x000045b8 in _dispatch_worker_thread (context=0x9550) at /Users/Accounts/mirko/src/libdispatch/src/queue.c:413 413 while (!(next = head->do_next)) { If I link the test with the system dispatch implementation it runs without problems. Is there a way to compile correctly the library? Thank you. -- Ciao, Mirko

2 1

Why polling event sources with a kevent receiving queue of size 1?
by cee1 19 Jul '10

19 Jul '10

Hi all, I've noticed libdispatch will poll event sources with an one-entry kevent receiving queue(queue_kevent.c:162, in function " _dispatch_mgr_invoke"). This will incurs more system calls and hence poorer performance. Why not poll event sources with a larger kevent receiving queue? Regards, -- cee1

3 2

fastpath() and slowpath() usage
by Mark Heily 17 Jul '10

17 Jul '10

I've noticed some strange usage of the fastpath() and slowpath() macros in the libdispatch sources. These are wrappers for the __builtin_expect() branch prediction macro and defined as: #define fastpath(x) ((typeof(x))__builtin_expect((long)(x), ~0l)) #define slowpath(x) ((typeof(x))__builtin_expect((long)(x), 0l)) Everything I have read about __builtin_expect() says that it should be used within a conditional expression, like this: if (__builtin_expect(foo == NULL, 0)) { /* fast path */ } else { /* slow path */ } There are several cases in libdispatch where the __builtin_expect() macro is used separately from the conditional. Here's one example from semaphore.c: dispatch_semaphore_t dispatch_get_thread_semaphore(void) { dispatch_semaphore_t dsema; dsema = fastpath(_dispatch_thread_getspecific(dispatch_sema4_key)); if (!dsema) { while (!(dsema = dispatch_semaphore_create(0))) { sleep(1); } } _dispatch_thread_setspecific(dispatch_sema4_key, NULL); return dsema; } Can anyone explain the reason for using __builtin_expect() in this manner, and what the practical effect is? Thanks, - Mark

2 1