[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH 5/5] include: add lock-less reference counting primitives
From: |
Samuel Thibault |
Subject: |
Re: [PATCH 5/5] include: add lock-less reference counting primitives |
Date: |
Wed, 21 May 2014 01:54:27 +0200 |
User-agent: |
Mutt/1.5.21+34 (58baf7c9f32f) (2010-12-30) |
Justus Winter, le Thu 15 May 2014 23:10:51 +0200, a écrit :
> * include/refcount.h: New file.
Ack.
> ---
> include/refcount.h | 263
> +++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 263 insertions(+)
> create mode 100644 include/refcount.h
>
> diff --git a/include/refcount.h b/include/refcount.h
> new file mode 100644
> index 0000000..5c3302d
> --- /dev/null
> +++ b/include/refcount.h
> @@ -0,0 +1,263 @@
> +/* 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_
> +
> +#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. */
> +static inline void
> +refcount_init (refcount_t *ref, unsigned int references)
> +{
> + *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. */
> +static inline unsigned int
> +refcount_ref (refcount_t *ref)
> +{
> + unsigned int r;
> + r = __atomic_add_fetch (ref, 1, __ATOMIC_RELAXED);
> + assert (r != UINT_MAX || !"refcount overflowed!");
> + 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. */
> +static inline 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. */
> +static inline 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. */
> +static inline void
> +refcounts_init (refcounts_t *ref, uint32_t hard, uint32_t weak)
> +{
> + 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. */
> +static inline void
> +refcounts_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;
> +}
> +
> +/* 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. */
> +static inline 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. */
> +static inline 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 = ~0, .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. */
> +static inline 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 = ~0 } };
> + 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. */
> +static inline void
> +refcounts_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;
> +}
> +
> +/* 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. */
> +static inline 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. */
> +static inline 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. */
> +static inline 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. */
> +static inline uint32_t
> +refcounts_weak_references (refcounts_t *ref)
> +{
> + struct references result;
> + refcounts_references (ref, &result);
> + return result.weak;
> +}
> +
> +#endif /* _HURD_REFCOUNT_H_ */
> --
> 2.0.0.rc0
>
--
Samuel
> Quelqu'un aurait-il une solution pour réinitialiser un MBR
Si tu veux qu'il soit complètement blanc (pas souhaitable, à mon avis) :
dd if=/dev/zero of=/dev/hda bs=512 count=1 (sous Linux)
-+- OT in Guide du linuxien (très) pervers - "Pour les K difficiles" -+-
- next round of patches, Justus Winter, 2014/05/15
- [PATCH 2/5] libihash: add hurd_ihash_get_load, Justus Winter, 2014/05/15
- [PATCH 5/5] include: add lock-less reference counting primitives, Justus Winter, 2014/05/15
- Re: [PATCH 5/5] include: add lock-less reference counting primitives,
Samuel Thibault <=
- [PATCH 1/5] libihash: fix typo, Justus Winter, 2014/05/15
- [PATCH 3/5] libihash: add hurd_ihash_value_valid, Justus Winter, 2014/05/15
- [PATCH 4/5] libihash: optimize lookup-or-insert operations, Justus Winter, 2014/05/15