1  /*
  2   * Copyright (C) 2015-2019 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 <functional>
 30  #include <stdio.h>
 31  #include <wtf/Atomics.h>
 32  #include <wtf/Threading.h>
 33  
 34  class Bitmap {
 35  public:
 36      Bitmap() { clearAll(); }
 37  
 38      inline void clearAll();
 39      inline bool concurrentTestAndSet(size_t n);
 40      inline size_t numBits() const { return words * wordSize; }
 41  
 42  private:
 43      static constexpr size_t Size = 4096*10;
 44  
 45      static constexpr unsigned wordSize = sizeof(uint8_t) * 8;
 46      static constexpr unsigned words = (Size + wordSize - 1) / wordSize;
 47      static constexpr uint8_t one = 1;
 48  
 49      uint8_t bits[words];
 50  };
 51  
 52  inline void Bitmap::clearAll()
 53  {
 54      memset(&bits, 0, sizeof(bits));
 55  }
 56  
 57  inline bool Bitmap::concurrentTestAndSet(size_t n)
 58  {
 59      uint8_t mask = one << (n % wordSize);
 60      size_t index = n / wordSize;
 61      uint8_t* wordPtr = &bits[index];
 62      uint8_t oldValue;
 63      do {
 64          oldValue = *wordPtr;
 65          if (oldValue & mask)
 66              return true;
 67      } while (!WTF::atomicCompareExchangeWeakRelaxed(wordPtr, oldValue, static_cast<uint8_t>(oldValue | mask)));
 68      return false;
 69  }
 70  
 71  struct Data {
 72      Bitmap* bitmap;
 73      int id;
 74      int numThreads;
 75  };
 76  
 77  static void setBitThreadFunc(void* p)
 78  {
 79      Data* data = reinterpret_cast<Data*>(p);
 80      Bitmap* bitmap = data->bitmap;
 81      size_t numBits = bitmap->numBits();
 82  
 83      // The computed start index here is heuristic that seems to maximize (anecdotally)
 84      // the chance for the CAS issue to manifest.
 85      size_t start = (numBits * (data->numThreads - data->id)) / data->numThreads;
 86  
 87      printf("   started Thread %d\n", data->id);
 88      for (size_t i = start; i < numBits; i++)
 89          while (!bitmap->concurrentTestAndSet(i)) { }
 90      for (size_t i = 0; i < start; i++)
 91          while (!bitmap->concurrentTestAndSet(i)) { }
 92  
 93      printf("   finished Thread %d\n", data->id);
 94  }
 95  
 96  void testCompareAndSwap()
 97  {
 98      Bitmap bitmap;
 99      const int numThreads = 5;
100      RefPtr<Thread> threads[numThreads];
101      Data data[numThreads];
102  
103      WTF::initialize();
104      
105      printf("Starting %d threads for CompareAndSwap test.  Test should complete without hanging.\n", numThreads);
106      for (int i = 0; i < numThreads; i++) {
107          data[i].bitmap = &bitmap;
108          data[i].id = i;
109          data[i].numThreads = numThreads;
110          threads[i] = Thread::create("setBitThreadFunc", std::bind(setBitThreadFunc, &data[i]));
111      }
112  
113      printf("Waiting for %d threads to join\n", numThreads);
114      for (int i = 0; i < numThreads; i++)
115          threads[i]->waitForCompletion();
116  
117      printf("PASS: CompareAndSwap test completed without a hang\n");
118  }