LCOV - code coverage report
Current view: top level - core/support - stack_lockfree.c (source / functions) Hit Total Coverage
Test: tmp.CaZ6RjdVn2 Lines: 40 40 100.0 %
Date: 2015-12-10 22:15:08 Functions: 4 4 100.0 %

          Line data    Source code
       1             : /*
       2             :  *
       3             :  * Copyright 2015, Google Inc.
       4             :  * All rights reserved.
       5             :  *
       6             :  * Redistribution and use in source and binary forms, with or without
       7             :  * modification, are permitted provided that the following conditions are
       8             :  * met:
       9             :  *
      10             :  *     * Redistributions of source code must retain the above copyright
      11             :  * notice, this list of conditions and the following disclaimer.
      12             :  *     * Redistributions in binary form must reproduce the above
      13             :  * copyright notice, this list of conditions and the following disclaimer
      14             :  * in the documentation and/or other materials provided with the
      15             :  * distribution.
      16             :  *     * Neither the name of Google Inc. nor the names of its
      17             :  * contributors may be used to endorse or promote products derived from
      18             :  * this software without specific prior written permission.
      19             :  *
      20             :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
      21             :  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
      22             :  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
      23             :  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
      24             :  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
      25             :  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
      26             :  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
      27             :  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
      28             :  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
      29             :  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
      30             :  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
      31             :  *
      32             :  */
      33             : 
      34             : #include "src/core/support/stack_lockfree.h"
      35             : 
      36             : #include <stdlib.h>
      37             : #include <string.h>
      38             : 
      39             : #include <grpc/support/port_platform.h>
      40             : #include <grpc/support/alloc.h>
      41             : #include <grpc/support/atm.h>
      42             : #include <grpc/support/log.h>
      43             : 
      44             : /* The lockfree node structure is a single architecture-level
      45             :    word that allows for an atomic CAS to set it up. */
      46             : struct lockfree_node_contents {
      47             :   /* next thing to look at. Actual index for head, next index otherwise */
      48             :   gpr_uint16 index;
      49             : #ifdef GPR_ARCH_64
      50             :   gpr_uint16 pad;
      51             :   gpr_uint32 aba_ctr;
      52             : #else
      53             : #ifdef GPR_ARCH_32
      54             :   gpr_uint16 aba_ctr;
      55             : #else
      56             : #error Unsupported bit width architecture
      57             : #endif
      58             : #endif
      59             : };
      60             : 
      61             : /* Use a union to make sure that these are in the same bits as an atm word */
      62             : typedef union lockfree_node {
      63             :   gpr_atm atm;
      64             :   struct lockfree_node_contents contents;
      65             : } lockfree_node;
      66             : 
      67             : #define ENTRY_ALIGNMENT_BITS 3 /* make sure that entries aligned to 8-bytes */
      68             : #define INVALID_ENTRY_INDEX                        \
      69             :   ((1 << 16) - 1) /* reserve this entry as invalid \
      70             :                     */
      71             : 
      72             : struct gpr_stack_lockfree {
      73             :   lockfree_node *entries;
      74             :   lockfree_node head; /* An atomic entry describing curr head */
      75             : 
      76             : #ifndef NDEBUG
      77             :   /* Bitmap of pushed entries to check for double-push or pop */
      78             :   gpr_atm pushed[(INVALID_ENTRY_INDEX + 1) / (8 * sizeof(gpr_atm))];
      79             : #endif
      80             : };
      81             : 
      82        8575 : gpr_stack_lockfree *gpr_stack_lockfree_create(size_t entries) {
      83             :   gpr_stack_lockfree *stack;
      84        8575 :   stack = gpr_malloc(sizeof(*stack));
      85             :   /* Since we only allocate 16 bits to represent an entry number,
      86             :    * make sure that we are within the desired range */
      87             :   /* Reserve the highest entry number as a dummy */
      88        8575 :   GPR_ASSERT(entries < INVALID_ENTRY_INDEX);
      89        8575 :   stack->entries = gpr_malloc_aligned(entries * sizeof(stack->entries[0]),
      90             :                                       ENTRY_ALIGNMENT_BITS);
      91             :   /* Clear out all entries */
      92        8575 :   memset(stack->entries, 0, entries * sizeof(stack->entries[0]));
      93        8575 :   memset(&stack->head, 0, sizeof(stack->head));
      94             : #ifndef NDEBUG
      95        8575 :   memset(&stack->pushed, 0, sizeof(stack->pushed));
      96             : #endif
      97             : 
      98             :   GPR_ASSERT(sizeof(stack->entries->atm) == sizeof(stack->entries->contents));
      99             : 
     100             :   /* Point the head at reserved dummy entry */
     101        8575 :   stack->head.contents.index = INVALID_ENTRY_INDEX;
     102        8575 :   return stack;
     103             : }
     104             : 
     105        8495 : void gpr_stack_lockfree_destroy(gpr_stack_lockfree *stack) {
     106        8495 :   gpr_free_aligned(stack->entries);
     107        8495 :   gpr_free(stack);
     108        8495 : }
     109             : 
     110   123821270 : int gpr_stack_lockfree_push(gpr_stack_lockfree *stack, int entry) {
     111             :   lockfree_node head;
     112             :   lockfree_node newhead;
     113             :   lockfree_node curent;
     114             :   lockfree_node newent;
     115             : 
     116             :   /* First fill in the entry's index and aba ctr for new head */
     117   123821270 :   newhead.contents.index = (gpr_uint16)entry;
     118             :   /* Also post-increment the aba_ctr */
     119   123821270 :   curent.atm = gpr_atm_no_barrier_load(&stack->entries[entry].atm);
     120   123821270 :   newhead.contents.aba_ctr = ++curent.contents.aba_ctr;
     121   123821270 :   gpr_atm_no_barrier_store(&stack->entries[entry].atm, curent.atm);
     122             : 
     123             : #ifndef NDEBUG
     124             :   /* Check for double push */
     125             :   {
     126   123821270 :     int pushed_index = entry / (int)(8 * sizeof(gpr_atm));
     127   123821270 :     int pushed_bit = entry % (int)(8 * sizeof(gpr_atm));
     128             :     gpr_atm old_val;
     129             : 
     130   123821270 :     old_val = gpr_atm_no_barrier_fetch_add(&stack->pushed[pushed_index],
     131             :                                            (gpr_atm)(1UL << pushed_bit));
     132   123821270 :     GPR_ASSERT((old_val & (gpr_atm)(1UL << pushed_bit)) == 0);
     133             :   }
     134             : #endif
     135             : 
     136             :   do {
     137             :     /* Atomically get the existing head value for use */
     138   123824793 :     head.atm = gpr_atm_no_barrier_load(&(stack->head.atm));
     139             :     /* Point to it */
     140   123824793 :     newent.atm = gpr_atm_no_barrier_load(&stack->entries[entry].atm);
     141   123824793 :     newent.contents.index = head.contents.index;
     142   123824793 :     gpr_atm_no_barrier_store(&stack->entries[entry].atm, newent.atm);
     143   125168503 :   } while (!gpr_atm_rel_cas(&(stack->head.atm), head.atm, newhead.atm));
     144             :   /* Use rel_cas above to make sure that entry index is set properly */
     145   123834552 :   return head.contents.index == INVALID_ENTRY_INDEX;
     146             : }
     147             : 
     148     8899775 : int gpr_stack_lockfree_pop(gpr_stack_lockfree *stack) {
     149             :   lockfree_node head;
     150             :   lockfree_node newhead;
     151             : 
     152             :   do {
     153     8899775 :     head.atm = gpr_atm_acq_load(&(stack->head.atm));
     154     8899775 :     if (head.contents.index == INVALID_ENTRY_INDEX) {
     155      238254 :       return -1;
     156             :     }
     157     8661130 :     newhead.atm =
     158     8661352 :         gpr_atm_no_barrier_load(&(stack->entries[head.contents.index].atm));
     159             : 
     160     8661352 :   } while (!gpr_atm_no_barrier_cas(&(stack->head.atm), head.atm, newhead.atm));
     161             : #ifndef NDEBUG
     162             :   /* Check for valid pop */
     163             :   {
     164     8655046 :     int pushed_index = head.contents.index / (8 * sizeof(gpr_atm));
     165     8655046 :     int pushed_bit = head.contents.index % (8 * sizeof(gpr_atm));
     166             :     gpr_atm old_val;
     167             : 
     168     8655046 :     old_val = gpr_atm_no_barrier_fetch_add(&stack->pushed[pushed_index],
     169             :                                            -(gpr_atm)(1UL << pushed_bit));
     170     8655046 :     GPR_ASSERT((old_val & (gpr_atm)(1UL << pushed_bit)) != 0);
     171             :   }
     172             : #endif
     173             : 
     174     8655046 :   return head.contents.index;
     175             : }

Generated by: LCOV version 1.11