altstack: New module
authorDan Good <dan@dancancode.com>
Tue, 26 Jan 2016 22:18:43 +0000 (22:18 +0000)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 29 Jan 2016 05:57:24 +0000 (16:27 +1030)
altstack - run a function with a dedicated stack, and then release the memory

Signed-off-by: Dan Good <dan@dancancode.com>
Makefile-ccan
ccan/altstack/LICENSE [new symlink]
ccan/altstack/_info [new file with mode: 0644]
ccan/altstack/altstack.c [new file with mode: 0644]
ccan/altstack/altstack.h [new file with mode: 0644]
ccan/altstack/test/run.c [new file with mode: 0644]

index 9469334e37bd6e30a28522b2417dac6da493e0f5..2c80720c9595af367c49c391b78cf43515f132ef 100644 (file)
@@ -33,6 +33,7 @@ MODS_NO_SRC := alignof \
 # No external dependencies, with C code:
 MODS_WITH_SRC := aga \
        agar \
+       altstack \
        antithread \
        antithread/alloc \
        asort \
diff --git a/ccan/altstack/LICENSE b/ccan/altstack/LICENSE
new file mode 120000 (symlink)
index 0000000..4f8ee74
--- /dev/null
@@ -0,0 +1 @@
+../../licenses/APACHE-2
\ No newline at end of file
diff --git a/ccan/altstack/_info b/ccan/altstack/_info
new file mode 100644 (file)
index 0000000..1b03770
--- /dev/null
@@ -0,0 +1,125 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ *
+ * altstack - run a function with a dedicated stack, and then release the memory
+ *
+ * C99 introduced variable length arrays to make the language easier to use
+ * and more efficient. Many regard VLA's with distrust due to fear of stack
+ * overflow. The same fear causes many to shy away from recursion.
+ *
+ * altstack seeks to liberate us from this fear. altstack creates a dedicated stack,
+ * limited to a specified maximum size, runs a given function using this stack, and
+ * afterwards releases the memory back to the system.
+ *
+ * altstack provides a way to obtain current stack usage and a way to fail gracefully.
+ *
+ * altstack is implemented for x86-64 only.
+ *
+ * Example:
+ *     // allocate a VLA on a dedicated stack and show memory usage
+ *     #include <assert.h>
+ *     #include <err.h>
+ *     #include <stdio.h>
+ *     #include <stdlib.h>
+ *     #include <string.h>
+ *     #include <unistd.h>
+ *     #include <ccan/altstack/altstack.h>
+ *
+ *     #define ok(x) ({ int __r = (x); if (__r == -1) err(1, #x); __r; })
+ *
+ *     char maps[128], rss[128];
+ *
+ *     static void stack_used(void) {
+ *             fprintf(stderr, "stack used: %ld\n", altstack_used());
+ *     }
+ *
+ *     static void *fn(void *arg)
+ *     {
+ *             ok(system(maps));
+ *
+ *             stack_used();
+ *             ok(system(rss));
+ *
+ *             char p[(long) arg];
+ *
+ *             stack_used();
+ *             ok(system(rss));
+ *
+ *             memset(p, 0, sizeof(p));
+ *
+ *             stack_used();
+ *             ok(system(rss));
+ *
+ *             return (void *) 0xaced;
+ *     }
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             long stk_max, vla_sz;
+ *             int ret;
+ *             void *out;
+ *
+ *             assert(argc == 3);
+ *             stk_max = strtol(argv[1], 0, 0) * 1024 * 1024;
+ *             vla_sz  = strtol(argv[2], 0, 0) * 1024 * 1024;
+ *             assert(stk_max > 0 && vla_sz > 0);
+ *
+ *             snprintf(maps, sizeof(maps), "egrep '\\[stack' /proc/%d/maps", getpid());
+ *             snprintf(rss,  sizeof(rss),  "egrep '^VmRSS' /proc/%d/status", getpid());
+ *
+ *             ok(system(maps));
+ *             ok(system(rss));
+ *
+ *             ret = altstack(stk_max, fn, (void *) vla_sz, &out);
+ *
+ *             ok(system(maps));
+ *             ok(system(rss));
+ *
+ *             if (ret)
+ *                     altstack_perror();
+ *             fprintf(stderr, "altstack return: %d, fn return: %p\n", ret, out);
+ *
+ *             return 0;
+ *     }
+ *     // $ ./foo 1024 512
+ *     // 7ffeb59a9000-7ffeb59ca000 rw-p 00000000 00:00 0                          [stack]
+ *     // VmRSS:       760 kB
+ *     // 7f9cb6005000-7f9cf6004000 rw-p 00000000 00:00 0                          [stack:25891]
+ *     // stack used: 56
+ *     // VmRSS:       760 kB
+ *     // stack used: 536870968
+ *     // VmRSS:       760 kB
+ *     // stack used: 536870968
+ *     // VmRSS:    525500 kB
+ *     // 7ffeb59a9000-7ffeb59ca000 rw-p 00000000 00:00 0                          [stack]
+ *     // VmRSS:      1332 kB
+ *     // altstack return: 0, fn return: 0xaced
+ *     //
+ *     // $ ./foo 512 1024
+ *     // 7ffd62bd0000-7ffd62bf1000 rw-p 00000000 00:00 0                          [stack]
+ *     // VmRSS:       700 kB
+ *     // 7f0d3bef6000-7f0d5bef5000 rw-p 00000000 00:00 0                          [stack:25900]
+ *     // stack used: 56
+ *     // VmRSS:       700 kB
+ *     // 7ffd62bd0000-7ffd62bf1000 rw-p 00000000 00:00 0                          [stack]
+ *     // VmRSS:      1336 kB
+ *     // (altstack@103) SIGSEGV caught
+ *     // altstack return: -1, fn return: (nil)
+ *
+ * License: APACHE-2
+ * Author: Dan Good <dan@dancancode.com>
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0)
+               return 0;
+
+       return 1;
+}
diff --git a/ccan/altstack/altstack.c b/ccan/altstack/altstack.c
new file mode 100644 (file)
index 0000000..6faf38f
--- /dev/null
@@ -0,0 +1,124 @@
+/* Licensed under Apache License v2.0 - see LICENSE file for details */
+#include "config.h"
+#include "altstack.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <setjmp.h>
+#include <signal.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/mman.h>
+
+static __thread char ebuf[ALTSTACK_ERR_MAXLEN];
+static __thread unsigned elen;
+
+#define bang(x)                                                        \
+       (elen += snprintf(ebuf + elen, sizeof(ebuf) - elen,     \
+                "%s(altstack@%d) %s%s%s",                      \
+                elen  ? "; " : "", __LINE__, (x),              \
+                errno ? ": " : "", errno ? strerror(errno) : ""))
+
+void altstack_perror(void)
+{
+       fprintf(stderr, "%s\n", ebuf);
+}
+
+char *altstack_geterr(void)
+{
+       return ebuf;
+}
+
+static __thread jmp_buf jmp;
+
+static void segvjmp(int signum)
+{
+       longjmp(jmp, 1);
+}
+
+static __thread void *rsp_save_[2];
+
+static ptrdiff_t rsp_save(unsigned i) {
+       assert(i < 2);
+       asm volatile ("movq %%rsp, %0" : "=g" (rsp_save_[i]));
+       return (char *) rsp_save_[0] - (char *) rsp_save_[i];
+}
+
+void altstack_rsp_save(void) {
+       rsp_save(0);
+}
+
+ptrdiff_t altstack_used(void) {
+       return rsp_save(1);
+}
+
+static __thread void *(*fn_)(void *);
+static __thread void *arg_, *out_;
+
+int altstack(rlim_t max, void *(*fn)(void *), void *arg, void **out)
+{
+       int ret = -1, undo = 0;
+       char *m;
+       struct rlimit rl_save;
+       struct sigaction sa_save;
+       int errno_save;
+
+       assert(max > 0 && fn);
+       #define ok(x, y) ({ long __r = (long) (x); if (__r == -1) { bang(#x); if (y) goto out; } __r; })
+
+       fn_  = fn;
+       arg_ = arg;
+       out_ = 0;
+       ebuf[elen = 0] = '\0';
+       if (out) *out = 0;
+
+       ok(getrlimit(RLIMIT_STACK, &rl_save), 1);
+       ok(setrlimit(RLIMIT_STACK, &(struct rlimit) { max, rl_save.rlim_max }), 1);
+       undo++;
+
+       ok(m = mmap(0, max, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_GROWSDOWN|MAP_NORESERVE, -1, 0), 1);
+       undo++;
+
+       if (setjmp(jmp) == 0) {
+               unsigned char sigstk[MINSIGSTKSZ];
+               stack_t ss = { .ss_sp = sigstk, .ss_size = sizeof(sigstk) };
+               struct sigaction sa = { .sa_handler = segvjmp, .sa_flags = SA_NODEFER|SA_RESETHAND|SA_ONSTACK };
+
+               ok(sigaltstack(&ss, 0), 1);
+               undo++;
+
+               sigemptyset(&sa.sa_mask);
+               ok(sigaction(SIGSEGV, &sa, &sa_save), 1);
+               undo++;
+
+               asm volatile ("movq %%rsp, %%r10\nmov %0, %%rsp\npush %%r10" : : "g" (m + max) : "r10");
+               rsp_save(0);
+               out_ = fn_(arg_);
+               asm volatile ("pop %rsp");
+               ret = 0;
+               if (out) *out = out_;
+       }
+       else {
+               errno = 0;
+               bang("SIGSEGV caught");
+               errno = EOVERFLOW;
+       }
+
+out:
+       errno_save = errno;
+
+       switch (undo) {
+       case 4:
+               ok(sigaction(SIGSEGV, &sa_save, 0), 0);
+       case 3:
+               ok(sigaltstack(&(stack_t) { .ss_flags = SS_DISABLE }, 0), 0);
+       case 2:
+               ok(munmap(m, max), 0);
+       case 1:
+               ok(setrlimit(RLIMIT_STACK, &rl_save), 0);
+       }
+
+       if (errno_save)
+               errno = errno_save;
+       return !ret && elen ? 1 : ret;
+}
diff --git a/ccan/altstack/altstack.h b/ccan/altstack/altstack.h
new file mode 100644 (file)
index 0000000..5570e7b
--- /dev/null
@@ -0,0 +1,114 @@
+/* Licensed under Apache License v2.0 - see LICENSE file for details */
+#ifndef CCAN_ALTSTACK_H
+#define CCAN_ALTSTACK_H
+#include "config.h"
+
+#if ! __x86_64__
+#error "This code expects the AMD64 ABI, but __x86_64__ is false."
+#endif
+
+#include <stddef.h>
+#include <sys/resource.h>
+
+#define ALTSTACK_ERR_MAXLEN 128
+
+/**
+ * altstack - run a function with a dedicated stack, and then release the memory
+ * @max: the maximum size of the new stack
+ * @fn: a function to run
+ * @arg: an argument passed to fn
+ * @out: where to store the return of fn, optional
+ *
+ * rlimit is set to @max, and an anonymous noreserve mapping is made.
+ * A jump buffer is setup and a signal handler established for SIGSEGV.
+ * The rsp register is set to the mapped address, with the old rsp value
+ * pushed onto the new stack. The provided @fn is called, with @arg as
+ * its only argument, from non-stack addresses. Once @fn returns,
+ * rsp is popped off the stack. If @out is non-null, it gets the return
+ * value from @fn. The region is unmapped and the other changes undone.
+ *
+ * Error messages are appended to a buffer available via altstack_geterr()
+ * and altstack_perror(). errno is set by the failing call, or set to
+ * EOVERFLOW in case SIGSEGV is caught.
+ *
+ * altstack() uses thread-local storage, and should not be nested.
+ *
+ * Example:
+ *     // permit recursion depth over a million
+ *     // a contrived example! (-O2 replaces the recursion with a loop)
+ *     #include <assert.h>
+ *     #include <stdio.h>
+ *     #include <stdlib.h>
+ *     #include <ccan/altstack/altstack.h>
+ *
+ *     unsigned depth;
+ *
+ *     static void dn(unsigned long i)
+ *     {
+ *             depth++;
+ *             if (i) dn(--i);
+ *     }
+ *
+ *     static void *wrap(void *i)
+ *     {
+ *             dn((unsigned long) i);
+ *             return 0;
+ *     }
+ *
+ *     #define MiB (1024UL*1024UL)
+ *     int main(int argc, char *argv[])
+ *     {
+ *             unsigned long n;
+ *             assert(argc == 2);
+ *             n = strtoul(argv[1], 0, 0);
+ *
+ *             if (altstack(32*MiB, wrap, (void *) n, 0) != 0)
+ *                     altstack_perror();
+ *
+ *             printf("%d\n", depth);
+ *
+ *             return 0;
+ *     }
+ *
+ * Returns: -1 on error; 0 on success; 1 on error after @fn returns
+ */
+int altstack(rlim_t max, void *(*fn)(void *), void *arg, void **out);
+
+/**
+ * altstack_perror - print error messages to stderr
+ */
+void altstack_perror(void);
+
+/**
+ * altstack_geterr - return the error buffer
+ *
+ * The error buffer is static thread-local storage.
+ * The buffer is reset with each altstack() call.
+ *
+ * Returns: pointer to the error buffer
+ */
+char *altstack_geterr(void);
+
+/**
+ * altstack_used - return amount of stack used
+ *
+ * This captures the current rsp value and returns
+ * the difference from the initial rsp value.
+ *
+ * Note: this can be used with any stack, including the original.
+ * When using with a non-altstack stack, call altstack_rsp_save()
+ * as early as possible to establish the initial value.
+ *
+ * Returns: difference of rsp values
+ */
+ptrdiff_t altstack_used(void);
+
+/**
+ * altstack_rsp_save - set initial rsp value
+ *
+ * Capture the current value of rsp for future altstack_used()
+ * calculations. altstack() also saves the initial rsp, so
+ * this should only be used in non-altstack contexts.
+ */
+void altstack_rsp_save(void);
+#endif
diff --git a/ccan/altstack/test/run.c b/ccan/altstack/test/run.c
new file mode 100644 (file)
index 0000000..adc1020
--- /dev/null
@@ -0,0 +1,144 @@
+#include <assert.h>
+#include <err.h>
+#include <errno.h>
+#include <setjmp.h>
+#include <signal.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <ccan/tap/tap.h>
+#include <ccan/altstack/altstack.h>
+#define _XOPEN_SOURCE 700
+#include <stdio.h>
+
+enum {
+       getrlimit_      = 1<<0,
+       setrlimit_      = 1<<1,
+       mmap_           = 1<<2,
+       sigaltstack_    = 1<<3,
+       sigaction_      = 1<<4,
+       munmap_         = 1<<5,
+};
+int fail, call1, call2;
+char *m_;
+rlim_t max_;
+#define e(x) (900+(x))
+#define seterr(x) (errno = e(x))
+#define setcall(x) ((call1 |= !errno ? (x) : 0), (call2 |= errno || out_ ? (x) : 0))
+#define getrlimit(...)         (fail&getrlimit_        ? (seterr(getrlimit_),          -1) : (setcall(getrlimit_),     getrlimit(__VA_ARGS__)))
+#define mmap(...)              (fail&mmap_             ? (seterr(mmap_),       (void *)-1) : (setcall(mmap_),          mmap(__VA_ARGS__)))
+#define munmap(a, b)           (fail&munmap_           ? (seterr(munmap_),             -1) : (setcall(munmap_),        munmap(m_=(a), max_=(b))))
+#define setrlimit(...)         (fail&setrlimit_        ? (seterr(setrlimit_),          -1) : (setcall(setrlimit_),     setrlimit(__VA_ARGS__)))
+#define sigaltstack(...)       (fail&sigaltstack_      ? (seterr(sigaltstack_),        -1) : (setcall(sigaltstack_),   sigaltstack(__VA_ARGS__)))
+#define sigaction(...)         (fail&sigaction_        ? (seterr(sigaction_),          -1) : (setcall(sigaction_),     sigaction(__VA_ARGS__)))
+
+#define KiB (1024UL)
+#define MiB (KiB*KiB)
+#define GiB (MiB*KiB)
+#define TiB (GiB*KiB)
+
+FILE *mystderr;
+#undef stderr
+#define stderr mystderr
+#undef ok
+#include <ccan/altstack/altstack.c>
+#undef ok
+
+long used;
+
+static void __attribute__((optimize("O0"))) dn(unsigned long i)
+{
+       if (used) used = altstack_used();
+       if (i) dn(--i);
+}
+static void *wrap(void *i)
+{
+       dn((unsigned long) i);
+       return wrap;
+}
+
+int main(void)
+{
+       plan_tests(16);
+
+#define chkfail(x, y, z, c1, c2) (call1 = 0, call2 = 0, errno = 0, ok1((fail = x) && (y) && errno == (z) && call1 == (c1) && call2 == (c2)));
+#define   chkok(   y, z, c1, c2) (call1 = 0, call2 = 0, errno = 0, fail = 0,     ok1((y) && errno == (z) && call1 == (c1) && call2 == (c2)));
+
+       chkfail(getrlimit_,     altstack(8*MiB, wrap, 0, 0) == -1, e(getrlimit_),
+               0,
+               0);
+
+       chkfail(setrlimit_,     altstack(8*MiB, wrap, 0, 0) == -1, e(setrlimit_),
+               getrlimit_,
+               0);
+
+       chkfail(mmap_,          altstack(8*MiB, wrap, 0, 0) == -1, e(mmap_),
+               getrlimit_|setrlimit_,
+               setrlimit_);
+
+       chkfail(sigaltstack_,   altstack(8*MiB, wrap, 0, 0) == -1, e(sigaltstack_),
+               getrlimit_|setrlimit_|mmap_,
+               setrlimit_|munmap_);
+
+       chkfail(sigaction_,     altstack(8*MiB, wrap, 0, 0) == -1, e(sigaction_),
+               getrlimit_|setrlimit_|mmap_|sigaltstack_,
+               setrlimit_|munmap_|sigaltstack_);
+
+       chkfail(munmap_,        altstack(8*MiB, wrap, 0, 0) ==  1, e(munmap_),
+               getrlimit_|setrlimit_|mmap_|sigaltstack_|sigaction_,
+               setrlimit_|sigaltstack_|sigaction_);
+       if (fail = 0, munmap(m_, max_) == -1)
+               err(1, "munmap");
+
+       chkok(                  altstack(1*MiB, wrap, (void *) 1000000, 0) == -1, EOVERFLOW,
+               getrlimit_|setrlimit_|mmap_|sigaltstack_|sigaction_,
+               setrlimit_|munmap_|sigaltstack_|sigaction_);
+
+       // be sure segv catch is repeatable (SA_NODEFER)
+       chkok(                  altstack(1*MiB, wrap, (void *) 1000000, 0) == -1, EOVERFLOW,
+               getrlimit_|setrlimit_|mmap_|sigaltstack_|sigaction_,
+               setrlimit_|munmap_|sigaltstack_|sigaction_);
+
+       used = 1;
+       chkfail(munmap_,        altstack(1*MiB, wrap, (void *) 1000000, 0) == -1, EOVERFLOW,
+               getrlimit_|setrlimit_|mmap_|sigaltstack_|sigaction_,
+               setrlimit_|sigaltstack_|sigaction_);
+       if (fail = 0, munmap(m_, max_) == -1)
+               err(1, "munmap");
+
+       ok1(used > 1*MiB-1*KiB && used < 1*MiB);
+
+       char *p;
+       for(p = altstack_geterr(); *p; p++)
+               if (*p >= '0' && *p <= '9')
+                       *p = '~';
+
+       #define estr "(altstack@~~~) SIGSEGV caught; (altstack@~~~) munmap(m, max): Unknown error ~~~"
+       ok1(strcmp(altstack_geterr(), estr) == 0);
+
+       char buf[ALTSTACK_ERR_MAXLEN*2] = {0};
+       if ((mystderr = fmemopen(buf, sizeof(buf), "w")) == NULL)
+               err(1, "fmemopen");
+
+       altstack_perror();
+       fflush(mystderr);
+       ok1(strcmp(buf, estr "\n") == 0);
+
+       used = 1;
+       chkok(                  altstack(8*MiB, wrap, (void *) 1000000, 0) == -1, EOVERFLOW,
+               getrlimit_|setrlimit_|mmap_|sigaltstack_|sigaction_,
+               setrlimit_|munmap_|sigaltstack_|sigaction_);
+
+       ok1(used > 8*MiB-8*KiB && used < 8*MiB);
+
+       used = 0;
+       chkok(                  altstack(8*MiB, wrap, (void *) 100000, 0) == 0, 0,
+               getrlimit_|setrlimit_|mmap_|sigaltstack_|sigaction_|munmap_,
+               setrlimit_|munmap_|sigaltstack_|sigaction_);
+
+       used = 1;
+       altstack_rsp_save();
+       dn(0);
+       ok1(used == 32);
+
+       return exit_status();
+}