On Wed, Apr 17, 2013 at 08:06:43PM -0400, Ted Unangst wrote:
> At some point, every young programmer hears a story about how you can
> use xor to store the pointers of a list. It's a stupid story for many
> reasons, not least of which is the fact that nobody ever does this.
> Sounds like a challenge.
>
> This diff doesn't actually implement anything like what you're
> probably thinking of when somebody says XORed list pointers. What I've
> done is create an alternate universe version of the SIMPLEQ queue.h
> macros that automatically XORs all the list pointers with a magic
> cookie stored in the list head.
>
> The reason we do this is because malloc and pool maintain their free
> lists as simple linked lists, with internal pointers. If the naughty
> people discover a use after free bug, this basically gives them a
> write anything to the kernel's memory ticket. That's bad. If we
> encrypt all the pointers, that overwrite suddenly becomes a lot less
> reliable. The cookie is stored in a different part of memory, we have to
> hope it doesn't leak out somehow.
>
> I'm not the first to think of this, apparently even my phone already
> does something similar. In fact, it may even be doing something
> better, but the approach taken here is drop in simple. Anywhere you
> have a simpleq list, now you can have an xor protected simpleq list.
>
> If you are concerned about performance, I recommend you upgrade to a
> computer with a hardware accelerated xor instruction.
By the only hardware accelarated operation my computer has is NAND...
-Ottto
>
> Index: kern/subr_pool.c
> ===================================================================
> RCS file: /cvs/src/sys/kern/subr_pool.c,v
> retrieving revision 1.118
> diff -u -p -r1.118 subr_pool.c
> --- kern/subr_pool.c 6 Apr 2013 13:41:11 -0000 1.118
> +++ kern/subr_pool.c 15 Apr 2013 13:06:34 -0000
> @@ -67,7 +67,7 @@ struct pool_item_header {
> /* Page headers */
> LIST_ENTRY(pool_item_header)
> ph_pagelist; /* pool page list */
> - SIMPLEQ_HEAD(,pool_item) ph_itemlist; /* chunk list for this page */
> + XSIMPLEQ_HEAD(,pool_item) ph_itemlist; /* chunk list for this page */
> RB_ENTRY(pool_item_header)
> ph_node; /* Off-page page headers */
> int ph_nmissing; /* # of chunks in use */
> @@ -80,7 +80,7 @@ struct pool_item_header {
> struct pool_item {
> u_int32_t pi_magic;
> /* Other entries use only this list entry */
> - SIMPLEQ_ENTRY(pool_item) pi_list;
> + XSIMPLEQ_ENTRY(pool_item) pi_list;
> };
>
> #ifdef POOL_DEBUG
> @@ -620,7 +620,7 @@ startover:
> /* Start the allocation process over. */
> goto startover;
> }
> - if ((v = pi = SIMPLEQ_FIRST(&ph->ph_itemlist)) == NULL) {
> + if ((v = pi = XSIMPLEQ_FIRST(&ph->ph_itemlist)) == NULL) {
> panic("pool_do_get: %s: page empty", pp->pr_wchan);
> }
> #ifdef DIAGNOSTIC
> @@ -653,7 +653,7 @@ startover:
> /*
> * Remove from item list.
> */
> - SIMPLEQ_REMOVE_HEAD(&ph->ph_itemlist, pi_list);
> + XSIMPLEQ_REMOVE_HEAD(&ph->ph_itemlist, pi_list);
> pp->pr_nitems--;
> pp->pr_nout++;
> if (ph->ph_nmissing == 0) {
> @@ -671,7 +671,7 @@ startover:
> LIST_INSERT_HEAD(&pp->pr_partpages, ph, ph_pagelist);
> }
> ph->ph_nmissing++;
> - if (SIMPLEQ_EMPTY(&ph->ph_itemlist)) {
> + if (XSIMPLEQ_EMPTY(&ph->ph_itemlist)) {
> #ifdef DIAGNOSTIC
> if (ph->ph_nmissing != pp->pr_itemsperpage) {
> panic("pool_do_get: %s: nmissing inconsistent",
> @@ -771,7 +771,7 @@ pool_do_put(struct pool *pp, void *v)
> }
> #endif /* DIAGNOSTIC */
>
> - SIMPLEQ_INSERT_HEAD(&ph->ph_itemlist, pi, pi_list);
> + XSIMPLEQ_INSERT_HEAD(&ph->ph_itemlist, pi, pi_list);
> ph->ph_nmissing--;
> pp->pr_nitems++;
> pp->pr_nout--;
> @@ -874,7 +874,7 @@ pool_prime_page(struct pool *pp, caddr_t
> * Insert page header.
> */
> LIST_INSERT_HEAD(&pp->pr_emptypages, ph, ph_pagelist);
> - SIMPLEQ_INIT(&ph->ph_itemlist);
> + XSIMPLEQ_INIT(&ph->ph_itemlist);
> ph->ph_page = storage;
> ph->ph_pagesize = pp->pr_alloc->pa_pagesz;
> ph->ph_nmissing = 0;
> @@ -909,7 +909,7 @@ pool_prime_page(struct pool *pp, caddr_t
> KASSERT(((((vaddr_t)pi) + ioff) & (align - 1)) == 0);
>
> /* Insert on page list */
> - SIMPLEQ_INSERT_TAIL(&ph->ph_itemlist, pi, pi_list);
> + XSIMPLEQ_INSERT_TAIL(&ph->ph_itemlist, pi, pi_list);
>
> #ifdef DIAGNOSTIC
> pi->pi_magic = poison_value(pi);
> @@ -1130,7 +1130,7 @@ pool_print_pagelist(struct pool_pagelist
> (*pr)("\t\tpage %p, nmissing %d\n",
> ph->ph_page, ph->ph_nmissing);
> #ifdef DIAGNOSTIC
> - SIMPLEQ_FOREACH(pi, &ph->ph_itemlist, pi_list) {
> + XSIMPLEQ_FOREACH(pi, &ph->ph_itemlist, pi_list) {
> if (pi->pi_magic != poison_value(pi)) {
> (*pr)("\t\t\titem %p, magic 0x%x\n",
> pi, pi->pi_magic);
> @@ -1281,9 +1281,9 @@ pool_chk_page(struct pool *pp, struct po
> return 1;
> }
>
> - for (pi = SIMPLEQ_FIRST(&ph->ph_itemlist), n = 0;
> + for (pi = XSIMPLEQ_FIRST(&ph->ph_itemlist), n = 0;
> pi != NULL;
> - pi = SIMPLEQ_NEXT(pi,pi_list), n++) {
> + pi = XSIMPLEQ_NEXT(&ph->ph_itemlist, pi, pi_list), n++) {
>
> #ifdef DIAGNOSTIC
> if (pi->pi_magic != poison_value(pi)) {
> @@ -1379,7 +1379,7 @@ pool_walk(struct pool *pp, int full,
> n = ph->ph_nmissing;
>
> do {
> - SIMPLEQ_FOREACH(pi, &ph->ph_itemlist, pi_list) {
> + XSIMPLEQ_FOREACH(pi, &ph->ph_itemlist, pi_list) {
> if (cp == (caddr_t)pi)
> break;
> }
> Index: kern/kern_malloc.c
> ===================================================================
> RCS file: /cvs/src/sys/kern/kern_malloc.c,v
> retrieving revision 1.99
> diff -u -p -r1.99 kern_malloc.c
> --- kern/kern_malloc.c 6 Apr 2013 03:53:25 -0000 1.99
> +++ kern/kern_malloc.c 15 Apr 2013 13:06:34 -0000
> @@ -41,6 +41,8 @@
> #include <sys/time.h>
> #include <sys/rwlock.h>
>
> +#include <dev/rndvar.h>
> +
> #include <uvm/uvm.h>
>
> static __inline__ long BUCKETINDX(size_t sz)
> @@ -132,7 +134,7 @@ struct kmem_freelist {
> int32_t kf_spare0;
> int16_t kf_type;
> int16_t kf_spare1;
> - SIMPLEQ_ENTRY(kmem_freelist) kf_flist;
> + XSIMPLEQ_ENTRY(kmem_freelist) kf_flist;
> };
>
> #ifdef DIAGNOSTIC
> @@ -221,7 +223,7 @@ malloc(unsigned long size, int type, int
> allocsize = round_page(size);
> else
> allocsize = 1 << indx;
> - if (SIMPLEQ_FIRST(&kbp->kb_freelist) == NULL) {
> + if (XSIMPLEQ_FIRST(&kbp->kb_freelist) == NULL) {
> npg = atop(round_page(allocsize));
> va = (caddr_t)uvm_km_kmemalloc_pla(kmem_map, NULL,
> (vsize_t)ptoa(npg), 0,
> @@ -273,7 +275,7 @@ malloc(unsigned long size, int type, int
> poison_mem(cp, allocsize);
> freep->kf_type = M_FREE;
> #endif /* DIAGNOSTIC */
> - SIMPLEQ_INSERT_HEAD(&kbp->kb_freelist, freep, kf_flist);
> + XSIMPLEQ_INSERT_HEAD(&kbp->kb_freelist, freep,
> kf_flist);
> if (cp <= va)
> break;
> cp -= allocsize;
> @@ -283,15 +285,15 @@ malloc(unsigned long size, int type, int
> freshalloc = 0;
> #endif
> }
> - freep = SIMPLEQ_FIRST(&kbp->kb_freelist);
> - SIMPLEQ_REMOVE_HEAD(&kbp->kb_freelist, kf_flist);
> + freep = XSIMPLEQ_FIRST(&kbp->kb_freelist);
> + XSIMPLEQ_REMOVE_HEAD(&kbp->kb_freelist, kf_flist);
> va = (caddr_t)freep;
> #ifdef DIAGNOSTIC
> savedtype = (unsigned)freep->kf_type < M_LAST ?
> memname[freep->kf_type] : "???";
> - if (freshalloc == 0 && SIMPLEQ_FIRST(&kbp->kb_freelist)) {
> + if (freshalloc == 0 && XSIMPLEQ_FIRST(&kbp->kb_freelist)) {
> int rv;
> - vaddr_t addr = (vaddr_t)SIMPLEQ_FIRST(&kbp->kb_freelist);
> + vaddr_t addr = (vaddr_t)XSIMPLEQ_FIRST(&kbp->kb_freelist);
>
> vm_map_lock(kmem_map);
> rv = uvm_map_checkprot(kmem_map, addr,
> @@ -420,7 +422,7 @@ free(void *addr, int type)
> */
> if (freep->kf_spare0 == poison_value(freep)) {
> struct kmem_freelist *fp;
> - SIMPLEQ_FOREACH(fp, &kbp->kb_freelist, kf_flist) {
> + XSIMPLEQ_FOREACH(fp, &kbp->kb_freelist, kf_flist) {
> if (addr != fp)
> continue;
> printf("multiply freed item %p\n", addr);
> @@ -453,7 +455,7 @@ free(void *addr, int type)
> wakeup(ksp);
> ksp->ks_inuse--;
> #endif
> - SIMPLEQ_INSERT_TAIL(&kbp->kb_freelist, freep, kf_flist);
> + XSIMPLEQ_INSERT_TAIL(&kbp->kb_freelist, freep, kf_flist);
> splx(s);
> }
>
> @@ -538,7 +540,7 @@ kmeminit(void)
> kmemusage = (struct kmemusage *) uvm_km_zalloc(kernel_map,
> (vsize_t)(nkmempages * sizeof(struct kmemusage)));
> for (indx = 0; indx < MINBUCKET + 16; indx++) {
> - SIMPLEQ_INIT(&bucket[indx].kb_freelist);
> + XSIMPLEQ_INIT(&bucket[indx].kb_freelist);
> }
> #ifdef KMEMSTATS
> for (indx = 0; indx < MINBUCKET + 16; indx++) {
> Index: sys/malloc.h
> ===================================================================
> RCS file: /cvs/src/sys/sys/malloc.h,v
> retrieving revision 1.104
> diff -u -p -r1.104 malloc.h
> --- sys/malloc.h 6 Apr 2013 03:53:25 -0000 1.104
> +++ sys/malloc.h 15 Apr 2013 13:06:34 -0000
> @@ -347,7 +347,7 @@ struct kmem_freelist;
> * Set of buckets for each size of memory block that is retained
> */
> struct kmembuckets {
> - SIMPLEQ_HEAD(, kmem_freelist) kb_freelist; /* list of free blocks */
> + XSIMPLEQ_HEAD(, kmem_freelist) kb_freelist; /* list of free blocks */
> u_int64_t kb_calls; /* total calls to allocate this size */
> u_int64_t kb_total; /* total number of blocks allocated */
> u_int64_t kb_totalfree; /* # of free elements in this bucket */
> Index: sys/queue.h
> ===================================================================
> RCS file: /cvs/src/sys/sys/queue.h,v
> retrieving revision 1.36
> diff -u -p -r1.36 queue.h
> --- sys/queue.h 11 Apr 2012 13:29:14 -0000 1.36
> +++ sys/queue.h 15 Apr 2013 13:06:34 -0000
> @@ -317,6 +317,84 @@ struct {
> \
> } while (0)
>
> /*
> + * XOR Simple queue definitions.
> + */
> +#define XSIMPLEQ_HEAD(name, type) \
> +struct name {
> \
> + struct type *sqx_first; /* first element */ \
> + struct type **sqx_last; /* addr of last next element */ \
> + unsigned long sqx_cookie; \
> +}
> +
> +#define XSIMPLEQ_ENTRY(type) \
> +struct { \
> + struct type *sqx_next; /* next element */ \
> +}
> +
> +/*
> + * Simple queue access methods.
> + */
> +#define XSIMPLEQ_XOR(head, ptr) ((typeof(ptr))((head)->sqx_cookie ^
> (unsigned long)(ptr)))
> +#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head,
> ((head)->sqx_first))
> +#define XSIMPLEQ_END(head) NULL
> +#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) ==
> XSIMPLEQ_END(head))
> +#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head,
> ((elm)->field.sqx_next))
> +
> +
> +#define XSIMPLEQ_FOREACH(var, head, field) \
> + for ((var) = XSIMPLEQ_FIRST(head); \
> + (var) != XSIMPLEQ_END(head); \
> + (var) = XSIMPLEQ_NEXT(head, var, field))
> +
> +#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar)
> \
> + for ((var) = XSIMPLEQ_FIRST(head); \
> + (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
> + (var) = (tvar))
> +
> +/*
> + * Simple queue functions.
> + */
> +#define XSIMPLEQ_INIT(head) do {
> \
> + (head)->sqx_cookie = arc4random(); \
> + if (sizeof(unsigned long) == 8) \
> + (head)->sqx_cookie |= ((unsigned long)arc4random()) <<
> sizeof(long) * 4; \
> + (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
> + (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
> +} while (0)
> +
> +#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
> + if (((elm)->field.sqx_next = (head)->sqx_first) == XSIMPLEQ_XOR(head,
> NULL)) \
> + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);
> \
> + (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
> +} while (0)
> +
> +#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
> + (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
> + *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm));
> \
> + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
> +} while (0)
> +
> +#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {
> \
> + if (((elm)->field.sqx_next = (listelm)->field.sqx_next) ==
> XSIMPLEQ_XOR(head, NULL)) \
> + (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);
> \
> + (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
> +} while (0)
> +
> +#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
> + if (((head)->sqx_first = XSIMPLEQ_XOR(head,
> (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
> + (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);
> \
> +} while (0)
> +
> +#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
> + if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
> + (elm)->field.sqx_next)->field.sqx_next) \
> + == XSIMPLEQ_XOR(head, NULL)) \
> + (head)->sqx_last = \
> + XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
> +} while (0)
> +
> +
> +/*
> * Tail queue definitions.
> */
> #define TAILQ_HEAD(name, type)
> \
>
