API/tests/CompareAndSwapTest.cpp

   1 /*
   2  * Copyright (C) 2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "CompareAndSwapTest.h"
  28
  29 #include <stdio.h>
  30 #include <wtf/Atomics.h>
  31 #include <wtf/Threading.h>
  32
  33 class Bitmap {
  34 public:
  35     Bitmap() { clearAll(); }
  36
  37     inline void clearAll();
  38     inline bool concurrentTestAndSet(size_t n);
  39     inline size_t numBits() const { return words * wordSize; }
  40
  41 private:
  42     static const size_t Size = 4096*10;
  43
  44     static const unsigned wordSize = sizeof(uint8_t) * 8;
  45     static const unsigned words = (Size + wordSize - 1) / wordSize;
  46     static const uint8_t one = 1;
  47
  48     uint8_t bits[words];
  49 };
  50
  51 inline void Bitmap::clearAll()
  52 {
  53     memset(&bits, 0, sizeof(bits));
  54 }
  55
  56 inline bool Bitmap::concurrentTestAndSet(size_t n)
  57 {
  58     uint8_t mask = one << (n % wordSize);
  59     size_t index = n / wordSize;
  60     uint8_t* wordPtr = &bits[index];
  61     uint8_t oldValue;
  62     do {
  63         oldValue = *wordPtr;
  64         if (oldValue & mask)
  65             return true;
  66     } while (!WTF::weakCompareAndSwap(wordPtr, oldValue, oldValue | mask));
  67     return false;
  68 }
  69
  70 struct Data {
  71     Bitmap* bitmap;
  72     int id;
  73     int numThreads;
  74 };
  75
  76 static void setBitThreadFunc(void* p)
  77 {
  78     Data* data = reinterpret_cast<Data*>(p);
  79     Bitmap* bitmap = data->bitmap;
  80     size_t numBits = bitmap->numBits();
  81
  82     // The computed start index here is heuristic that seems to maximize (anecdotally)
  83     // the chance for the CAS issue to manifest.
  84     size_t start = (numBits * (data->numThreads - data->id)) / data->numThreads;
  85
  86     printf("   started Thread %d\n", data->id);
  87     for (size_t i = start; i < numBits; i++)
  88         while (!bitmap->concurrentTestAndSet(i)) { }
  89     for (size_t i = 0; i < start; i++)
  90         while (!bitmap->concurrentTestAndSet(i)) { }
  91
  92     printf("   finished Thread %d\n", data->id);
  93 }
  94
  95 void testCompareAndSwap()
  96 {
  97     Bitmap bitmap;
  98     const int numThreads = 5;
  99     ThreadIdentifier threadIDs[numThreads];
 100     Data data[numThreads];
 101
 102     WTF::initializeThreading();
 103
 104     printf("Starting %d threads for CompareAndSwap test.  Test should complete without hanging.\n", numThreads);
 105     for (int i = 0; i < numThreads; i++) {
 106         data[i].bitmap = &bitmap;
 107         data[i].id = i;
 108         data[i].numThreads = numThreads;
 109         std::function<void()> threadFunc = std::bind(setBitThreadFunc, &data[i]);
 110         threadIDs[i] = createThread("setBitThreadFunc", threadFunc);
 111     }
 112
 113     printf("Waiting for %d threads to join\n", numThreads);
 114     for (int i = 0; i < numThreads; i++)
 115         waitForThreadCompletion(threadIDs[i]);
 116
 117     printf("PASS: CompareAndSwap test completed without a hang\n");
 118 }