--- a/hotspot/src/share/vm/utilities/taskqueue.hpp Wed Jun 30 11:52:10 2010 -0400
+++ b/hotspot/src/share/vm/utilities/taskqueue.hpp Thu Jul 01 21:40:45 2010 -0700
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2001, 2009, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -109,8 +109,9 @@
public:
TaskQueueSuper() : _bottom(0), _age() {}
- // Return true if the TaskQueue contains any tasks.
- bool peek() { return _bottom != _age.top(); }
+ // Return true if the TaskQueue contains/does not contain any tasks.
+ bool peek() const { return _bottom != _age.top(); }
+ bool is_empty() const { return size() == 0; }
// Return an estimate of the number of elements in the queue.
// The "careful" version admits the possibility of pop_local/pop_global
@@ -165,18 +166,16 @@
void initialize();
- // Push the task "t" on the queue. Returns "false" iff the queue is
- // full.
+ // Push the task "t" on the queue. Returns "false" iff the queue is full.
inline bool push(E t);
- // If succeeds in claiming a task (from the 'local' end, that is, the
- // most recently pushed task), returns "true" and sets "t" to that task.
- // Otherwise, the queue is empty and returns false.
+ // Attempts to claim a task from the "local" end of the queue (the most
+ // recently pushed). If successful, returns true and sets t to the task;
+ // otherwise, returns false (the queue is empty).
inline bool pop_local(E& t);
- // If succeeds in claiming a task (from the 'global' end, that is, the
- // least recently pushed task), returns "true" and sets "t" to that task.
- // Otherwise, the queue is empty and returns false.
+ // Like pop_local(), but uses the "global" end of the queue (the least
+ // recently pushed).
bool pop_global(E& t);
// Delete any resource associated with the queue.
@@ -198,7 +197,6 @@
template<class E, unsigned int N>
void GenericTaskQueue<E, N>::initialize() {
_elems = NEW_C_HEAP_ARRAY(E, N);
- guarantee(_elems != NULL, "Allocation failed.");
}
template<class E, unsigned int N>
@@ -289,7 +287,87 @@
FREE_C_HEAP_ARRAY(E, _elems);
}
-// Inherits the typedef of "Task" from above.
+// OverflowTaskQueue is a TaskQueue that also includes an overflow stack for
+// elements that do not fit in the TaskQueue.
+//
+// Three methods from super classes are overridden:
+//
+// initialize() - initialize the super classes and create the overflow stack
+// push() - push onto the task queue or, if that fails, onto the overflow stack
+// is_empty() - return true if both the TaskQueue and overflow stack are empty
+//
+// Note that size() is not overridden--it returns the number of elements in the
+// TaskQueue, and does not include the size of the overflow stack. This
+// simplifies replacement of GenericTaskQueues with OverflowTaskQueues.
+template<class E, unsigned int N = TASKQUEUE_SIZE>
+class OverflowTaskQueue: public GenericTaskQueue<E, N>
+{
+public:
+ typedef GrowableArray<E> overflow_t;
+ typedef GenericTaskQueue<E, N> taskqueue_t;
+
+ OverflowTaskQueue();
+ ~OverflowTaskQueue();
+ void initialize();
+
+ inline overflow_t* overflow_stack() const { return _overflow_stack; }
+
+ // Push task t onto the queue or onto the overflow stack. Return true.
+ inline bool push(E t);
+
+ // Attempt to pop from the overflow stack; return true if anything was popped.
+ inline bool pop_overflow(E& t);
+
+ inline bool taskqueue_empty() const { return taskqueue_t::is_empty(); }
+ inline bool overflow_empty() const { return overflow_stack()->is_empty(); }
+ inline bool is_empty() const {
+ return taskqueue_empty() && overflow_empty();
+ }
+
+private:
+ overflow_t* _overflow_stack;
+};
+
+template <class E, unsigned int N>
+OverflowTaskQueue<E, N>::OverflowTaskQueue()
+{
+ _overflow_stack = NULL;
+}
+
+template <class E, unsigned int N>
+OverflowTaskQueue<E, N>::~OverflowTaskQueue()
+{
+ if (_overflow_stack != NULL) {
+ delete _overflow_stack;
+ _overflow_stack = NULL;
+ }
+}
+
+template <class E, unsigned int N>
+void OverflowTaskQueue<E, N>::initialize()
+{
+ taskqueue_t::initialize();
+ assert(_overflow_stack == NULL, "memory leak");
+ _overflow_stack = new (ResourceObj::C_HEAP) GrowableArray<E>(10, true);
+}
+
+template <class E, unsigned int N>
+bool OverflowTaskQueue<E, N>::push(E t)
+{
+ if (!taskqueue_t::push(t)) {
+ overflow_stack()->push(t);
+ }
+ return true;
+}
+
+template <class E, unsigned int N>
+bool OverflowTaskQueue<E, N>::pop_overflow(E& t)
+{
+ if (overflow_empty()) return false;
+ t = overflow_stack()->pop();
+ return true;
+}
+
class TaskQueueSetSuper: public CHeapObj {
protected:
static int randomParkAndMiller(int* seed0);
@@ -323,11 +401,11 @@
T* queue(uint n);
- // The thread with queue number "queue_num" (and whose random number seed
- // is at "seed") is trying to steal a task from some other queue. (It
- // may try several queues, according to some configuration parameter.)
- // If some steal succeeds, returns "true" and sets "t" the stolen task,
- // otherwise returns false.
+ // The thread with queue number "queue_num" (and whose random number seed is
+ // at "seed") is trying to steal a task from some other queue. (It may try
+ // several queues, according to some configuration parameter.) If some steal
+ // succeeds, returns "true" and sets "t" to the stolen task, otherwise returns
+ // false.
bool steal(uint queue_num, int* seed, E& t);
bool peek();
@@ -507,7 +585,7 @@
uint localBot = _bottom;
// This value cannot be N-1. That can only occur as a result of
// the assignment to bottom in this method. If it does, this method
- // resets the size( to 0 before the next call (which is sequential,
+ // resets the size to 0 before the next call (which is sequential,
// since this is pop_local.)
uint dirty_n_elems = dirty_size(localBot, _age.top());
assert(dirty_n_elems != N - 1, "Shouldn't be possible...");
@@ -533,8 +611,7 @@
}
}
-typedef oop Task;
-typedef GenericTaskQueue<Task> OopTaskQueue;
+typedef GenericTaskQueue<oop> OopTaskQueue;
typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet;
#ifdef _MSC_VER
@@ -615,35 +692,8 @@
#pragma warning(pop)
#endif
-typedef GenericTaskQueue<StarTask> OopStarTaskQueue;
+typedef OverflowTaskQueue<StarTask> OopStarTaskQueue;
typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet;
-typedef size_t RegionTask; // index for region
-typedef GenericTaskQueue<RegionTask> RegionTaskQueue;
-typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet;
-
-class RegionTaskQueueWithOverflow: public CHeapObj {
- protected:
- RegionTaskQueue _region_queue;
- GrowableArray<RegionTask>* _overflow_stack;
-
- public:
- RegionTaskQueueWithOverflow() : _overflow_stack(NULL) {}
- // Initialize both stealable queue and overflow
- void initialize();
- // Save first to stealable queue and then to overflow
- void save(RegionTask t);
- // Retrieve first from overflow and then from stealable queue
- bool retrieve(RegionTask& region_index);
- // Retrieve from stealable queue
- bool retrieve_from_stealable_queue(RegionTask& region_index);
- // Retrieve from overflow
- bool retrieve_from_overflow(RegionTask& region_index);
- bool is_empty();
- bool stealable_is_empty();
- bool overflow_is_empty();
- uint stealable_size() { return _region_queue.size(); }
- RegionTaskQueue* task_queue() { return &_region_queue; }
-};
-
-#define USE_RegionTaskQueueWithOverflow
+typedef OverflowTaskQueue<size_t> RegionTaskQueue;
+typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet;