diff options
Diffstat (limited to 'libshouldbeinlibc')
| -rw-r--r-- | libshouldbeinlibc/Makefile | 8 | ||||
| -rw-r--r-- | libshouldbeinlibc/refcount.c | 23 | ||||
| -rw-r--r-- | libshouldbeinlibc/refcount.h | 326 |
3 files changed, 355 insertions, 2 deletions
diff --git a/libshouldbeinlibc/Makefile b/libshouldbeinlibc/Makefile index 14a7939d..633d60eb 100644 --- a/libshouldbeinlibc/Makefile +++ b/libshouldbeinlibc/Makefile @@ -27,9 +27,13 @@ SRCS = termsize.c timefmt.c exec-reauth.c maptime-funcs.c \ idvec-impgids.c idvec-verify.c idvec-rep.c \ ugids.c ugids-argp.c ugids-rep.c ugids-verify.c ugids-subtract.c \ ugids-auth.c ugids-xinl.c ugids-merge.c ugids-imply.c ugids-posix.c \ - ugids-verify-auth.c nullauth.c + ugids-verify-auth.c nullauth.c \ + refcount.c \ + installhdrs = idvec.h timefmt.h maptime.h \ - wire.h portinfo.h portxlate.h cacheq.h ugids.h nullauth.h + wire.h portinfo.h portxlate.h cacheq.h ugids.h nullauth.h \ + refcount.h \ + installhdrsubdir = . OBJS = $(SRCS:.c=.o) diff --git a/libshouldbeinlibc/refcount.c b/libshouldbeinlibc/refcount.c new file mode 100644 index 00000000..17e01c53 --- /dev/null +++ b/libshouldbeinlibc/refcount.c @@ -0,0 +1,23 @@ +/* Lock-less reference counting primitives + + Copyright (C) 2014 Free Software Foundation, Inc. + + Written by Justus Winter <4winter@informatik.uni-hamburg.de> + + This file is part of the GNU Hurd. + + The GNU Hurd is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + The GNU Hurd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the GNU Hurd. If not, see <http://www.gnu.org/licenses/>. */ + +#define REFCOUNT_DEFINE_EI +#include "refcount.h" diff --git a/libshouldbeinlibc/refcount.h b/libshouldbeinlibc/refcount.h new file mode 100644 index 00000000..e8b0f5bc --- /dev/null +++ b/libshouldbeinlibc/refcount.h @@ -0,0 +1,326 @@ +/* Lock-less reference counting primitives + + Copyright (C) 2014 Free Software Foundation, Inc. + + Written by Justus Winter <4winter@informatik.uni-hamburg.de> + + This file is part of the GNU Hurd. + + The GNU Hurd is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2, or (at + your option) any later version. + + The GNU Hurd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the GNU Hurd. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef _HURD_REFCOUNT_H_ +#define _HURD_REFCOUNT_H_ + +#ifdef REFCOUNT_DEFINE_EI +#define REFCOUNT_EI +#else +#define REFCOUNT_EI __extern_inline +#endif + +#include <assert.h> +#include <limits.h> +#include <stdint.h> + +/* Simple reference counting. */ + +/* An opaque type. You must not access these values directly. */ +typedef unsigned int refcount_t; + +/* Initialize REF with REFERENCES. REFERENCES must not be zero. */ +REFCOUNT_EI void +refcount_init (refcount_t *ref, unsigned int references) +{ + assert (references > 0 || !"references must not be zero!"); + *ref = references; +} + +/* Increment REF. Return the result of the operation. This function + uses atomic operations. It is not required to serialize calls to + this function. + + This is the unsafe version of refcount_ref. refcount_ref also + checks for use-after-free errors. When in doubt, use that one + instead. */ +REFCOUNT_EI unsigned int +refcount_unsafe_ref (refcount_t *ref) +{ + unsigned int r; + r = __atomic_add_fetch (ref, 1, __ATOMIC_RELAXED); + assert (r != UINT_MAX || !"refcount overflowed!"); + return r; +} + +/* Increment REF. Return the result of the operation. This function + uses atomic operations. It is not required to serialize calls to + this function. */ +REFCOUNT_EI unsigned int +refcount_ref (refcount_t *ref) +{ + unsigned int r; + r = refcount_unsafe_ref (ref); + assert (r != 1 || !"refcount detected use-after-free!"); + return r; +} + +/* Decrement REF. Return the result of the operation. This function + uses atomic operations. It is not required to serialize calls to + this function. */ +REFCOUNT_EI unsigned int +refcount_deref (refcount_t *ref) +{ + unsigned int r; + r = __atomic_sub_fetch (ref, 1, __ATOMIC_RELAXED); + assert (r != UINT_MAX || !"refcount underflowed!"); + return r; +} + +/* Return REF. This function uses atomic operations. It is not + required to serialize calls to this function. */ +REFCOUNT_EI unsigned int +refcount_references (refcount_t *ref) +{ + return __atomic_load_n (ref, __ATOMIC_RELAXED); +} + +/* Reference counting with weak references. */ + +/* An opaque type. You must not access these values directly. */ +typedef union _references refcounts_t; + +/* Instead, the functions manipulating refcounts_t values write the + results into this kind of objects. */ +struct references { + /* We chose the layout of this struct so that when it is used in the + union _references, the hard reference counts occupy the least + significant bits. We rely on this layout for atomic promotion + and demotion of references. See refcounts_promote and + refcounts_demote for details. */ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + uint32_t hard; + uint32_t weak; +#else + uint32_t weak; + uint32_t hard; +#endif +}; + +/* We use a union to convert struct reference values to uint64_t which + we can manipulate atomically. While this behavior is not + guaranteed by the C standard, it is supported by all major + compilers. */ +union _references { + struct references references; + uint64_t value; +}; + +/* Initialize REF with HARD and WEAK references. HARD and WEAK must + not both be zero. */ +REFCOUNT_EI void +refcounts_init (refcounts_t *ref, uint32_t hard, uint32_t weak) +{ + assert ((hard != 0 || weak != 0) || !"references must not both be zero!"); + ref->references = (struct references) { .hard = hard, .weak = weak }; +} + +/* Increment the hard reference count of REF. If RESULT is not NULL, + the result of the operation is written there. This function uses + atomic operations. It is not required to serialize calls to this + function. + + This is the unsafe version of refcounts_ref. refcounts_ref also + checks for use-after-free errors. When in doubt, use that one + instead. */ +REFCOUNT_EI void +refcounts_unsafe_ref (refcounts_t *ref, struct references *result) +{ + const union _references op = { .references = { .hard = 1 } }; + union _references r; + r.value = __atomic_add_fetch (&ref->value, op.value, __ATOMIC_RELAXED); + assert (r.references.hard != UINT32_MAX || !"refcount overflowed!"); + if (result) + *result = r.references; +} + +/* Increment the hard reference count of REF. If RESULT is not NULL, + the result of the operation is written there. This function uses + atomic operations. It is not required to serialize calls to this + function. */ +REFCOUNT_EI void +refcounts_ref (refcounts_t *ref, struct references *result) +{ + struct references r; + refcounts_unsafe_ref (ref, &r); + assert (! (r.hard == 1 && r.weak == 0) + || !"refcount detected use-after-free!"); + if (result) + *result = r; +} + +/* Decrement the hard reference count of REF. If RESULT is not NULL, + the result of the operation is written there. This function uses + atomic operations. It is not required to serialize calls to this + function. */ +REFCOUNT_EI void +refcounts_deref (refcounts_t *ref, struct references *result) +{ + const union _references op = { .references = { .hard = 1 } }; + union _references r; + r.value = __atomic_sub_fetch (&ref->value, op.value, __ATOMIC_RELAXED); + assert (r.references.hard != UINT32_MAX || !"refcount underflowed!"); + if (result) + *result = r.references; +} + +/* Promote a weak reference to a hard reference. If RESULT is not + NULL, the result of the operation is written there. This function + uses atomic operations. It is not required to serialize calls to + this function. */ +REFCOUNT_EI void +refcounts_promote (refcounts_t *ref, struct references *result) +{ + /* To promote a weak reference, we need to atomically subtract 1 + from the weak reference count, and add 1 to the hard reference + count. + + We can subtract by 1 by adding the two's complement of 1 = ~0 to + a fixed-width value, discarding the overflow. + + We do the same in our uint64_t value, but we have chosen the + layout of struct references so that when it is used in the union + _references, the weak reference counts occupy the most + significant bits. When we add ~0 to the weak references, the + overflow will be discarded as unsigned arithmetic is modulo 2^n. + So we just add a hard reference. In combination, this is the + desired operation. */ + const union _references op = + { .references = { .weak = ~0U, .hard = 1} }; + union _references r; + r.value = __atomic_add_fetch (&ref->value, op.value, __ATOMIC_RELAXED); + assert (r.references.hard != UINT32_MAX || !"refcount overflowed!"); + assert (r.references.weak != UINT32_MAX || !"refcount underflowed!"); + if (result) + *result = r.references; +} + +/* Demote a hard reference to a weak reference. If RESULT is not + NULL, the result of the operation is written there. This function + uses atomic operations. It is not required to serialize calls to + this function. */ +REFCOUNT_EI void +refcounts_demote (refcounts_t *ref, struct references *result) +{ + /* To demote a hard reference, we need to atomically subtract 1 from + the hard reference count, and add 1 to the weak reference count. + + We can subtract by 1 by adding the two's complement of 1 = ~0 to + a fixed-width value, discarding the overflow. + + We do the same in our uint64_t value, but we have chosen the + layout of struct references so that when it is used in the union + _references, the hard reference counts occupy the least + significant bits. When we add ~0 to the hard references, it will + overflow into the weak references. This is the desired + operation. */ + const union _references op = { .references = { .hard = ~0U } }; + union _references r; + r.value = __atomic_add_fetch (&ref->value, op.value, __ATOMIC_RELAXED); + assert (r.references.hard != UINT32_MAX || !"refcount underflowed!"); + assert (r.references.weak != UINT32_MAX || !"refcount overflowed!"); + if (result) + *result = r.references; +} + +/* Increment the weak reference count of REF. If RESULT is not NULL, + the result of the operation is written there. This function uses + atomic operations. It is not required to serialize calls to this + function. + + This is the unsafe version of refcounts_ref_weak. + refcounts_ref_weak also checks for use-after-free errors. When in + doubt, use that one instead. */ +REFCOUNT_EI void +refcounts_unsafe_ref_weak (refcounts_t *ref, struct references *result) +{ + const union _references op = { .references = { .weak = 1 } }; + union _references r; + r.value = __atomic_add_fetch (&ref->value, op.value, __ATOMIC_RELAXED); + assert (r.references.weak != UINT32_MAX || !"refcount overflowed!"); + if (result) + *result = r.references; +} + +/* Increment the weak reference count of REF. If RESULT is not NULL, + the result of the operation is written there. This function uses + atomic operations. It is not required to serialize calls to this + function. */ +REFCOUNT_EI void +refcounts_ref_weak (refcounts_t *ref, struct references *result) +{ + struct references r; + refcounts_unsafe_ref_weak (ref, &r); + assert (! (r.hard == 0 && r.weak == 1) + || !"refcount detected use-after-free!"); + if (result) + *result = r; +} + +/* Decrement the weak reference count of REF. If RESULT is not NULL, + the result of the operation is written there. This function uses + atomic operations. It is not required to serialize calls to this + function. */ +REFCOUNT_EI void +refcounts_deref_weak (refcounts_t *ref, struct references *result) +{ + const union _references op = { .references = { .weak = 1 } }; + union _references r; + r.value = __atomic_sub_fetch (&ref->value, op.value, __ATOMIC_RELAXED); + assert (r.references.weak != UINT32_MAX || !"refcount underflowed!"); + if (result) + *result = r.references; +} + +/* Store the current reference counts of REF in RESULT. This function + uses atomic operations. It is not required to serialize calls to + this function. */ +REFCOUNT_EI void +refcounts_references (refcounts_t *ref, struct references *result) +{ + union _references r; + r.value =__atomic_load_n (&ref->value, __ATOMIC_RELAXED); + *result = r.references; +} + +/* Return the hard reference count of REF. This function uses atomic + operations. It is not required to serialize calls to this + function. */ +REFCOUNT_EI uint32_t +refcounts_hard_references (refcounts_t *ref) +{ + struct references result; + refcounts_references (ref, &result); + return result.hard; +} + +/* Return the weak reference count of REF. This function uses atomic + operations. It is not required to serialize calls to this + function. */ +REFCOUNT_EI uint32_t +refcounts_weak_references (refcounts_t *ref) +{ + struct references result; + refcounts_references (ref, &result); + return result.weak; +} + +#endif /* _HURD_REFCOUNT_H_ */ |