queue_test-inl.h 12 KB
Newer Older
1
/*
2
 * Copyright (c) 2014-2015, Siemens AG. All rights reserved.
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef CONTAINERS_CPP_TEST_QUEUE_TEST_INL_H_
#define CONTAINERS_CPP_TEST_QUEUE_TEST_INL_H_

#include <algorithm>
#include <vector>

namespace embb {
namespace containers {
namespace test {
template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::QueueTest() :
38 39 40 41 42 43 44 45 46 47
  n_threads(static_cast<int>(partest::TestSuite::GetDefaultNumThreads())),
  n_queue_size(
    static_cast<int>(partest::TestSuite::GetDefaultNumIterations()) *
    MIN_TOTAL_PRODUCE_CONSUME_COUNT),
  n_total_produce_consume_count(n_queue_size),
  n_producers(1),
  n_consumers(1),
  next_producer_id(0),
  next_consumer_id(0),
  n_producer_elements(
Marcus Winter committed
48
    static_cast<int>(partest::TestSuite::GetDefaultNumIterations() *
49
    MIN_ENQ_ELEMENTS)) {
50 51 52 53 54
  CreateUnit("QueueTestSingleThreadEnqueueDequeue").
  Pre(&QueueTest::QueueTestSingleThreadEnqueueDequeue_Pre, this).
  Add(&QueueTest::QueueTestSingleThreadEnqueueDequeue_ThreadMethod, this).
  Post(&QueueTest::QueueTestSingleThreadEnqueueDequeue_Post, this);
  CreateUnit("QueueTestTwoThreadsSingleProducerSingleConsumer").
55 56 57 58 59 60 61 62
  Pre(&QueueTest::QueueTestSingleProducerSingleConsumer_Pre, this).
  Add(&QueueTest::QueueTestSingleProducerSingleConsumer_ThreadMethod,
    this,
    2,
    static_cast<size_t>(n_total_produce_consume_count)).
  Post(&QueueTest::QueueTestSingleProducerSingleConsumer_Post, this);

#ifdef _MSC_VER
63 64 65
#pragma warning(push)
#pragma warning(disable:4127)
#endif
66 67 68 69 70
  if (MultipleProducers == true && MultipleConsumers == true) {
    // MP/MC
    n_producers = n_threads / 2;
    n_consumers = n_threads / 2;
#ifdef _MSC_VER
71 72
#pragma warning(pop)
#endif
73 74 75 76 77 78 79 80 81 82 83
    CreateUnit("QueueTestOrderMultipleProducerMultipleConsumer").
      Pre(&QueueTest::QueueTestOrderMPMC_Pre, this).
      Add(&QueueTest::QueueTestOrderMPMC_ConsumerThreadMethod,
      this,
      static_cast<size_t>(n_consumers),
      static_cast<size_t>(1)).
      Add(&QueueTest::QueueTestOrderMPMC_ProducerThreadMethod,
      this,
      static_cast<size_t>(n_producers),
      static_cast<size_t>(1)).
      Post(&QueueTest::QueueTestOrderMPMC_Post, this);
84 85 86 87 88
  }
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
89 90
QueueTestOrderMPMC_Pre() {
  queue = new Queue_t(static_cast<size_t>(n_producer_elements));
91
  embb_internal_thread_index_reset();
92 93 94 95 96 97 98 99 100
  next_producer_id = 0;
  next_consumer_id = 0;
  consumers.clear();
  producers.clear();
  for (size_t p = 0; p < static_cast<size_t>(n_producers); ++p) {
    producers.push_back(Producer(queue, p, n_producer_elements));
  }
  for (size_t c = 0; c < static_cast<size_t>(n_consumers); ++c) {
    consumers.push_back(Consumer(queue, n_producers, n_producer_elements));
101 102 103 104 105
  }
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
106 107
QueueTestOrderMPMC_Post() {
  delete queue;
Marcus Winter committed
108 109
  // Tally for all elements enqueued by all producers,
  // initialized with all 0:
110
  ::std::vector<unsigned char> total_tally;
Marcus Winter committed
111 112
  size_t n_elements_total =
    static_cast<size_t>(n_producers * n_producer_elements);
113 114 115 116 117 118 119
  for (size_t i = 0; i < n_elements_total / 8; ++i) {
    total_tally.push_back(0);
  }
  // Collect all dequeued element flags from consumers:
  for (size_t c = 0; c < static_cast<size_t>(n_consumers); ++c) {
    for (size_t e = 0; e < n_elements_total / 8; ++e) {
      total_tally[e] |= consumers[c].Tally()[e];
120 121
    }
  }
Marcus Winter committed
122 123
  // Test if all elements have been dequeued by any
  // consumer.
124
  // To avoid static cast warning:
Marcus Winter committed
125
  for (size_t t = 0;
126 127 128 129
       t < static_cast<size_t>(n_producers * n_producer_elements / 8);
       ++t) {
    PT_ASSERT_EQ_MSG(total_tally[t], 0xff,
      "missing dequeued elements");
130 131 132 133 134
  }
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
135 136 137 138
QueueTestOrderMPMC_ProducerThreadMethod() {
  size_t p_id = next_producer_id.FetchAndAdd(1);
  producers[p_id].Run();
}
139

140 141 142 143 144 145
template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
QueueTestOrderMPMC_ConsumerThreadMethod() {
  size_t c_id = next_consumer_id.FetchAndAdd(1);
  consumers[c_id].Run();
}
146

147 148 149
template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::Producer::
Run() {
Marcus Winter committed
150
  // Enqueue pairs of (producer id, counter):
151 152 153 154 155
  for (int i = 0; i < n_producer_elements; ++i) {
    while (!q->TryEnqueue(element_t(producer_id, i))) {
      embb::base::Thread::CurrentYield();
    }
  }
Marcus Winter committed
156
  // Enqueue -1 as terminator element of this producer:
157 158
  while (!q->TryEnqueue(element_t(producer_id, -1))) {
    embb::base::Thread::CurrentYield();
159
  }
160
}
161

162 163 164
template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::Consumer::
Consumer(Queue_t * const queue, int numProducers, int numProducerElements) :
Marcus Winter committed
165
  q(queue),
166 167 168 169 170 171
  n_producers(numProducers),
  n_producer_elements(numProducerElements) {
  for (int p_id = 0; p_id < n_producers; ++p_id) {
    // Initialize last value dequeued from producers with
    // below-minimum value:
    sequence_number.push_back(-1);
Marcus Winter committed
172
    // Initialize element tally for producer with all 0,
173 174 175 176 177 178
    // 8 flags / char:
    for (int i = 0; i < n_producer_elements / 8; ++i) {
      consumer_tally.push_back(0);
    }
  }
}
179

180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::Consumer::
Run() {
  element_t element;
  size_t producerId;
  // To avoid compiler warning
  bool forever = true;
  while (forever) {
    if (!q->TryDequeue(element)) {
      continue;
    }
    if (element.second < 0) {
      break;
    }
    producerId = element.first;
    // Assert on dequeued element:
    PT_ASSERT_LT_MSG(producerId, static_cast<size_t>(n_producers),
Marcus Winter committed
197
      "Invalid producer id in dequeue");
198
    PT_ASSERT_LT_MSG(sequence_number[producerId], element.second,
Marcus Winter committed
199
      "Invalid element sequence");
200 201 202 203 204 205 206 207 208 209
    // Store last value received from the element's producer:
    sequence_number[producerId] = element.second;
    const size_t pos((producerId * n_producer_elements) +
      static_cast<size_t>(element.second));
    // Test dequeued element's position flag: tally[pos] == 1
    PT_ASSERT_EQ_MSG(consumer_tally[pos / 8] & (0x80 >> (pos % 8)), 0,
      "Element dequeued twice");
    // Set flag at dequeued element's position:
    // tally[pos] = 1
    consumer_tally[pos / 8] |= (0x80 >> (pos % 8));
210 211 212 213 214
  }
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
215
QueueTestSingleProducerSingleConsumer_Pre() {
216
  embb_internal_thread_index_reset();
217
  queue = new Queue_t(static_cast<size_t>(n_queue_size));
218 219 220 221 222 223 224 225 226
  thread_selector_producer = -1;
  produce_count = 0;
  consume_count = 0;
  consumed_elements.clear();
  produced_elements.clear();
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
227
QueueTestSingleProducerSingleConsumer_Post() {
228 229 230 231 232 233 234 235 236 237 238 239 240
  embb_atomic_memory_barrier();
  ::std::sort(consumed_elements.begin(), consumed_elements.end());
  ::std::sort(produced_elements.begin(), produced_elements.end());
  PT_ASSERT(consumed_elements.size() == produced_elements.size());
  for (unsigned int i = 0;
    i != static_cast<unsigned int>(consumed_elements.size()); i++) {
    PT_ASSERT(consumed_elements[i] == produced_elements[i]);
  }
  delete queue;
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
241
QueueTestSingleProducerSingleConsumer_ThreadMethod() {
242 243 244 245 246 247 248 249 250 251 252
  unsigned int thread_index;
  int return_val = embb_internal_thread_index(&thread_index);
  PT_ASSERT(return_val == EMBB_SUCCESS);
  if (thread_selector_producer == -1) {
    int expected = -1;
    thread_selector_producer.CompareAndSwap(expected,
      static_cast<int>(thread_index));
    while (thread_selector_producer == -1) {}
  }
  if (static_cast<unsigned int>(thread_selector_producer.Load()) ==
    thread_index) {
253 254
    // we are the producer
    while (produce_count >= n_queue_size) { }
255

256
    element_t random_var(0, rand() % 10000);
257 258 259 260 261
    bool success = queue->TryEnqueue(random_var);
    PT_ASSERT(success == true);
    produce_count++;
    produced_elements.push_back(random_var);
  } else {
262 263
    // we are the consumer
    while (consume_count < n_total_produce_consume_count) {
264 265 266
      consume_count++;
      while (produce_count == 0) {}

267
      element_t consumed;
268 269 270 271 272 273 274 275 276 277 278
      bool success = queue->TryDequeue(consumed);
      PT_ASSERT(success == true);
      produce_count--;
      consumed_elements.push_back(consumed);
    }
  }
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
QueueTestSingleThreadEnqueueDequeue_ThreadMethod() {
unknown committed
279
  // Enqueue the expected amount of elements
280 281
  for (int i = 0; i != n_queue_size; ++i) {
    bool success = queue->TryEnqueue(element_t(0, i * 133));
282 283
    PT_ASSERT(success == true);
  }
unknown committed
284 285 286 287 288 289 290 291 292

  // Some queues may allow enqueueing more elements than their capacity
  // permits, so try to enqueue additional elements until the queue is full
  int oversized_count = n_queue_size;
  while ( queue->TryEnqueue(element_t(0, oversized_count * 133)) ) {
    ++oversized_count;
  }
  // Oversized amount should not be larger than the original capacity
  PT_ASSERT_LT(oversized_count, 2 * n_queue_size);
Tobias Fuchs committed
293

unknown committed
294
  // Dequeue the expected amount of elements
295 296
  for (int i = 0; i != n_queue_size; ++i) {
    element_t dequ(0, -1);
297 298
    bool success = queue->TryDequeue(dequ);
    PT_ASSERT(success == true);
299
    PT_ASSERT(dequ.second == i * 133);
300
  }
unknown committed
301 302 303 304 305 306 307 308 309 310 311 312 313 314 315

  // Dequeue any elements enqueued above the original capacity
  for (int i = n_queue_size; i != oversized_count; ++i) {
    element_t dequ(0, -1);
    bool success = queue->TryDequeue(dequ);
    PT_ASSERT(success == true);
    PT_ASSERT(dequ.second == i * 133);
  }

  // Ensure the queue is now empty
  {
    element_t dequ;
    bool success = queue->TryDequeue(dequ);
    PT_ASSERT(success == false);
  }
316 317 318 319 320
}

template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
QueueTestSingleThreadEnqueueDequeue_Pre() {
321
  queue = new Queue_t(static_cast<size_t>(n_queue_size));
322
}
323

324 325 326 327 328 329 330 331 332 333
template<typename Queue_t, bool MultipleProducers, bool MultipleConsumers>
void QueueTest<Queue_t, MultipleProducers, MultipleConsumers>::
QueueTestSingleThreadEnqueueDequeue_Post() {
  delete queue;
}
} // namespace test
} // namespace containers
} // namespace embb

#endif  // CONTAINERS_CPP_TEST_QUEUE_TEST_INL_H_