ck_hp.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*
    2  * Copyright 2010-2015 Samy Al Bahra.
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  * 1. Redistributions of source code must retain the above copyright
    9  *    notice, this list of conditions and the following disclaimer.
   10  * 2. Redistributions in binary form must reproduce the above copyright
   11  *    notice, this list of conditions and the following disclaimer in the
   12  *    documentation and/or other materials provided with the distribution.
   13  *
   14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   24  * SUCH DAMAGE.
   25  */
   26 
   27 /*
   28  * (c) Copyright 2008, IBM Corporation.
   29  * Licensed under the Apache License, Version 2.0 (the "License");
   30  * you may not use this file except in compliance with the License.
   31  * You may obtain a copy of the License at
   32  *
   33  * http://www.apache.org/licenses/LICENSE-2.0
   34  *
   35  * Unless required by applicable law or agreed to in writing, software
   36  * distributed under the License is distributed on an "AS IS" BASIS,
   37  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   38  * See the License for the specific language governing permissions and
   39  * limitations under the License.
   40  */
   41 
   42 /*
   43  * This is an implementation of hazard pointers as detailed in:
   44  *   http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf
   45  *
   46  * This API provides a publishing mechanism that defers destruction of
   47  * hazard pointers until it is safe to do so. Preventing arbitrary re-use
   48  * protects against the ABA problem and provides safe memory reclamation.
   49  * The implementation was derived from the Hazard Pointers implementation
   50  * from the Amino CBBS project. It has been heavily modified for Concurrency
   51  * Kit.
   52  */
   53 
   54 #include <ck_backoff.h>
   55 #include <ck_cc.h>
   56 #include <ck_hp.h>
   57 #include <ck_pr.h>
   58 #include <ck_stack.h>
   59 #include <ck_stdbool.h>
   60 #include <ck_stddef.h>
   61 #include <ck_stdlib.h>
   62 #include <ck_string.h>
   63 
   64 CK_STACK_CONTAINER(struct ck_hp_record, global_entry, ck_hp_record_container)
   65 CK_STACK_CONTAINER(struct ck_hp_hazard, pending_entry, ck_hp_hazard_container)
   66 
   67 void
   68 ck_hp_init(struct ck_hp *state,
   69            unsigned int degree,
   70            unsigned int threshold,
   71            ck_hp_destructor_t destroy)
   72 {
   73 
   74         state->threshold = threshold;
   75         state->degree = degree;
   76         state->destroy = destroy;
   77         state->n_subscribers = 0;
   78         state->n_free = 0;
   79         ck_stack_init(&state->subscribers);
   80         ck_pr_fence_store();
   81 
   82         return;
   83 }
   84 
   85 void
   86 ck_hp_set_threshold(struct ck_hp *state, unsigned int threshold)
   87 {
   88 
   89         ck_pr_store_uint(&state->threshold, threshold);
   90         return;
   91 }
   92 
   93 struct ck_hp_record *
   94 ck_hp_recycle(struct ck_hp *global)
   95 {
   96         struct ck_hp_record *record;
   97         ck_stack_entry_t *entry;
   98         int state;
   99 
  100         if (ck_pr_load_uint(&global->n_free) == 0)
  101                 return NULL;
  102 
  103         CK_STACK_FOREACH(&global->subscribers, entry) {
  104                 record = ck_hp_record_container(entry);
  105 
  106                 if (ck_pr_load_int(&record->state) == CK_HP_FREE) {
  107                         ck_pr_fence_load();
  108                         state = ck_pr_fas_int(&record->state, CK_HP_USED);
  109                         if (state == CK_HP_FREE) {
  110                                 ck_pr_dec_uint(&global->n_free);
  111                                 return record;
  112                         }
  113                 }
  114         }
  115 
  116         return NULL;
  117 }
  118 
  119 void
  120 ck_hp_unregister(struct ck_hp_record *entry)
  121 {
  122 
  123         entry->n_pending = 0;
  124         entry->n_peak = 0;
  125         entry->n_reclamations = 0;
  126         ck_stack_init(&entry->pending);
  127         ck_pr_fence_store();
  128         ck_pr_store_int(&entry->state, CK_HP_FREE);
  129         ck_pr_inc_uint(&entry->global->n_free);
  130         return;
  131 }
  132 
  133 void
  134 ck_hp_register(struct ck_hp *state,
  135     struct ck_hp_record *entry,
  136     void **pointers)
  137 {
  138 
  139         entry->state = CK_HP_USED;
  140         entry->global = state;
  141         entry->pointers = pointers;
  142         entry->n_pending = 0;
  143         entry->n_peak = 0;
  144         entry->n_reclamations = 0;
  145         memset(pointers, 0, state->degree * sizeof(void *));
  146         ck_stack_init(&entry->pending);
  147         ck_pr_fence_store();
  148         ck_stack_push_upmc(&state->subscribers, &entry->global_entry);
  149         ck_pr_inc_uint(&state->n_subscribers);
  150         return;
  151 }
  152 
  153 static int
  154 hazard_compare(const void *a, const void *b)
  155 {
  156         void * const *x;
  157         void * const *y;
  158 
  159         x = a;
  160         y = b;
  161         return ((*x > *y) - (*x < *y));
  162 }
  163 
  164 CK_CC_INLINE static bool
  165 ck_hp_member_scan(ck_stack_entry_t *entry, unsigned int degree, void *pointer)
  166 {
  167         struct ck_hp_record *record;
  168         unsigned int i;
  169         void *hazard;
  170 
  171         do {
  172                 record = ck_hp_record_container(entry);
  173                 if (ck_pr_load_int(&record->state) == CK_HP_FREE)
  174                         continue;
  175 
  176                 if (ck_pr_load_ptr(&record->pointers) == NULL)
  177                         continue;
  178 
  179                 for (i = 0; i < degree; i++) {
  180                         hazard = ck_pr_load_ptr(&record->pointers[i]);
  181                         if (hazard == pointer)
  182                                 return (true);
  183                 }
  184         } while ((entry = CK_STACK_NEXT(entry)) != NULL);
  185 
  186         return (false);
  187 }
  188 
  189 CK_CC_INLINE static void *
  190 ck_hp_member_cache(struct ck_hp *global, void **cache, unsigned int *n_hazards)
  191 {
  192         struct ck_hp_record *record;
  193         ck_stack_entry_t *entry;
  194         unsigned int hazards = 0;
  195         unsigned int i;
  196         void *pointer;
  197 
  198         CK_STACK_FOREACH(&global->subscribers, entry) {
  199                 record = ck_hp_record_container(entry);
  200                 if (ck_pr_load_int(&record->state) == CK_HP_FREE)
  201                         continue;
  202 
  203                 if (ck_pr_load_ptr(&record->pointers) == NULL)
  204                         continue;
  205 
  206                 for (i = 0; i < global->degree; i++) {
  207                         if (hazards > CK_HP_CACHE)
  208                                 break;
  209 
  210                         pointer = ck_pr_load_ptr(&record->pointers[i]);
  211                         if (pointer != NULL)
  212                                 cache[hazards++] = pointer;
  213                 }
  214         }
  215 
  216         *n_hazards = hazards;
  217         return (entry);
  218 }
  219 
  220 void
  221 ck_hp_reclaim(struct ck_hp_record *thread)
  222 {
  223         struct ck_hp_hazard *hazard;
  224         struct ck_hp *global = thread->global;
  225         unsigned int n_hazards;
  226         void **cache, *marker, *match;
  227         ck_stack_entry_t *previous, *entry, *next;
  228 
  229         /* Store as many entries as possible in local array. */
  230         cache = thread->cache;
  231         marker = ck_hp_member_cache(global, cache, &n_hazards);
  232 
  233         /*
  234          * In theory, there is an n such that (n * (log n) ** 2) < np.
  235          */
  236         qsort(cache, n_hazards, sizeof(void *), hazard_compare);
  237 
  238         previous = NULL;
  239         CK_STACK_FOREACH_SAFE(&thread->pending, entry, next) {
  240                 hazard = ck_hp_hazard_container(entry);
  241                 match = bsearch(&hazard->pointer, cache, n_hazards,
  242                                   sizeof(void *), hazard_compare);
  243                 if (match != NULL) {
  244                         previous = entry;
  245                         continue;
  246                 }
  247 
  248                 if (marker != NULL &&
  249                     ck_hp_member_scan(marker, global->degree, hazard->pointer)) {
  250                         previous = entry;
  251                         continue;
  252                 }
  253 
  254                 thread->n_pending -= 1;
  255 
  256                 /* Remove from the pending stack. */
  257                 if (previous)
  258                         CK_STACK_NEXT(previous) = CK_STACK_NEXT(entry);
  259                 else
  260                         CK_STACK_FIRST(&thread->pending) = CK_STACK_NEXT(entry);
  261 
  262                 /* The entry is now safe to destroy. */
  263                 global->destroy(hazard->data);
  264                 thread->n_reclamations++;
  265         }
  266 
  267         return;
  268 }
  269 
  270 void
  271 ck_hp_retire(struct ck_hp_record *thread,
  272     struct ck_hp_hazard *hazard,
  273     void *data,
  274     void *pointer)
  275 {
  276 
  277         ck_pr_store_ptr(&hazard->pointer, pointer);
  278         ck_pr_store_ptr(&hazard->data, data);
  279         ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);
  280 
  281         thread->n_pending += 1;
  282         if (thread->n_pending > thread->n_peak)
  283                 thread->n_peak = thread->n_pending;
  284 
  285         return;
  286 }
  287 
  288 void
  289 ck_hp_free(struct ck_hp_record *thread,
  290     struct ck_hp_hazard *hazard,
  291     void *data,
  292     void *pointer)
  293 {
  294         struct ck_hp *global;
  295 
  296         global = ck_pr_load_ptr(&thread->global);
  297         ck_pr_store_ptr(&hazard->data, data);
  298         ck_pr_store_ptr(&hazard->pointer, pointer);
  299         ck_stack_push_spnc(&thread->pending, &hazard->pending_entry);
  300 
  301         thread->n_pending += 1;
  302         if (thread->n_pending > thread->n_peak)
  303                 thread->n_peak = thread->n_pending;
  304 
  305         if (thread->n_pending >= global->threshold)
  306                 ck_hp_reclaim(thread);
  307 
  308         return;
  309 }
  310 
  311 void
  312 ck_hp_purge(struct ck_hp_record *thread)
  313 {
  314         ck_backoff_t backoff = CK_BACKOFF_INITIALIZER;
  315 
  316         while (thread->n_pending > 0) {
  317                 ck_hp_reclaim(thread);
  318                 if (thread->n_pending > 0)
  319                         ck_backoff_eb(&backoff);
  320         }
  321 
  322         return;
  323 }
Cache object: 6801a81086cb4790067320cd25878972
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/contrib/ck/src/ck_hp.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/ck/src/ck_hp.c
