hotspot/src/share/vm/utilities/growableArray.hpp
author tonyp
Wed, 19 Jan 2011 19:30:42 -0500
changeset 7923 fc200fcd4e05
parent 7397 5b173b4ca846
child 10547 ea4a2ec31ae2
permissions -rw-r--r--
6977804: G1: remove the zero-filling thread Summary: This changeset removes the zero-filling thread from G1 and collapses the two free region lists we had before (the "free" and "unclean" lists) into one. The new free list uses the new heap region sets / lists abstractions that we'll ultimately use it to keep track of all regions in the heap. A heap region set was also introduced for the humongous regions. Finally, this change increases the concurrency between the thread that completes freeing regions (after a cleanup pause) and the rest of the system (before we'd have to wait for said thread to complete before allocating a new region). The changest also includes a lot of refactoring and code simplification. Reviewed-by: jcoomes, johnc

/*
 * Copyright (c) 1997, 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
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#ifndef SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
#define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP

#include "memory/allocation.hpp"
#include "memory/allocation.inline.hpp"
#include "utilities/debug.hpp"
#include "utilities/globalDefinitions.hpp"
#include "utilities/top.hpp"

// A growable array.

/*************************************************************************/
/*                                                                       */
/*     WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING   */
/*                                                                       */
/* Should you use GrowableArrays to contain handles you must be certain  */
/* the the GrowableArray does not outlive the HandleMark that contains   */
/* the handles. Since GrowableArrays are typically resource allocated    */
/* the following is an example of INCORRECT CODE,                        */
/*                                                                       */
/* ResourceMark rm;                                                      */
/* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size);         */
/* if (blah) {                                                           */
/*    while (...) {                                                      */
/*      HandleMark hm;                                                   */
/*      ...                                                              */
/*      Handle h(THREAD, some_oop);                                      */
/*      arr->append(h);                                                  */
/*    }                                                                  */
/* }                                                                     */
/* if (arr->length() != 0 ) {                                            */
/*    oop bad_oop = arr->at(0)(); // Handle is BAD HERE.                 */
/*    ...                                                                */
/* }                                                                     */
/*                                                                       */
/* If the GrowableArrays you are creating is C_Heap allocated then it    */
/* hould not old handles since the handles could trivially try and       */
/* outlive their HandleMark. In some situations you might need to do     */
/* this and it would be legal but be very careful and see if you can do  */
/* the code in some other manner.                                        */
/*                                                                       */
/*************************************************************************/

// To call default constructor the placement operator new() is used.
// It should be empty (it only returns the passed void* pointer).
// The definition of placement operator new(size_t, void*) in the <new>.

#include <new>

// Need the correct linkage to call qsort without warnings
extern "C" {
  typedef int (*_sort_Fn)(const void *, const void *);
}

class GenericGrowableArray : public ResourceObj {
 protected:
  int    _len;          // current length
  int    _max;          // maximum length
  Arena* _arena;        // Indicates where allocation occurs:
                        //   0 means default ResourceArea
                        //   1 means on C heap
                        //   otherwise, allocate in _arena
#ifdef ASSERT
  int    _nesting;      // resource area nesting at creation
  void   set_nesting();
  void   check_nesting();
#else
#define  set_nesting();
#define  check_nesting();
#endif

  // Where are we going to allocate memory?
  bool on_C_heap() { return _arena == (Arena*)1; }
  bool on_stack () { return _arena == NULL;      }
  bool on_arena () { return _arena >  (Arena*)1;  }

  // This GA will use the resource stack for storage if c_heap==false,
  // Else it will use the C heap.  Use clear_and_deallocate to avoid leaks.
  GenericGrowableArray(int initial_size, int initial_len, bool c_heap) {
    _len = initial_len;
    _max = initial_size;
    assert(_len >= 0 && _len <= _max, "initial_len too big");
    _arena = (c_heap ? (Arena*)1 : NULL);
    set_nesting();
    assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are");
    assert(!on_stack() ||
           (allocated_on_res_area() || allocated_on_stack()),
           "growable array must be on stack if elements are not on arena and not on C heap");
  }

  // This GA will use the given arena for storage.
  // Consider using new(arena) GrowableArray<T> to allocate the header.
  GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
    _len = initial_len;
    _max = initial_size;
    assert(_len >= 0 && _len <= _max, "initial_len too big");
    _arena = arena;
    assert(on_arena(), "arena has taken on reserved value 0 or 1");
    // Relax next assert to allow object allocation on resource area,
    // on stack or embedded into an other object.
    assert(allocated_on_arena() || allocated_on_stack(),
           "growable array must be on arena or on stack if elements are on arena");
  }

  void* raw_allocate(int elementSize);

  // some uses pass the Thread explicitly for speed (4990299 tuning)
  void* raw_allocate(Thread* thread, int elementSize) {
    assert(on_stack(), "fast ResourceObj path only");
    return (void*)resource_allocate_bytes(thread, elementSize * _max);
  }
};

template<class E> class GrowableArray : public GenericGrowableArray {
 private:
  E*     _data;         // data array

  void grow(int j);
  void raw_at_put_grow(int i, const E& p, const E& fill);
  void  clear_and_deallocate();
 public:
  GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
    _data = (E*)raw_allocate(thread, sizeof(E));
    for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
  }

  GrowableArray(int initial_size, bool C_heap = false) : GenericGrowableArray(initial_size, 0, C_heap) {
    _data = (E*)raw_allocate(sizeof(E));
    for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
  }

  GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false) : GenericGrowableArray(initial_size, initial_len, C_heap) {
    _data = (E*)raw_allocate(sizeof(E));
    int i = 0;
    for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
    for (; i < _max; i++) ::new ((void*)&_data[i]) E();
  }

  GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
    _data = (E*)raw_allocate(sizeof(E));
    int i = 0;
    for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
    for (; i < _max; i++) ::new ((void*)&_data[i]) E();
  }

  GrowableArray() : GenericGrowableArray(2, 0, false) {
    _data = (E*)raw_allocate(sizeof(E));
    ::new ((void*)&_data[0]) E();
    ::new ((void*)&_data[1]) E();
  }

                                // Does nothing for resource and arena objects
  ~GrowableArray()              { if (on_C_heap()) clear_and_deallocate(); }

  void  clear()                 { _len = 0; }
  int   length() const          { return _len; }
  void  trunc_to(int l)         { assert(l <= _len,"cannot increase length"); _len = l; }
  bool  is_empty() const        { return _len == 0; }
  bool  is_nonempty() const     { return _len != 0; }
  bool  is_full() const         { return _len == _max; }
  DEBUG_ONLY(E* data_addr() const      { return _data; })

  void print();

  int append(const E& elem) {
    check_nesting();
    if (_len == _max) grow(_len);
    int idx = _len++;
    _data[idx] = elem;
    return idx;
  }

  void append_if_missing(const E& elem) {
    if (!contains(elem)) append(elem);
  }

  E at(int i) const {
    assert(0 <= i && i < _len, "illegal index");
    return _data[i];
  }

  E* adr_at(int i) const {
    assert(0 <= i && i < _len, "illegal index");
    return &_data[i];
  }

  E first() const {
    assert(_len > 0, "empty list");
    return _data[0];
  }

  E top() const {
    assert(_len > 0, "empty list");
    return _data[_len-1];
  }

  void push(const E& elem) { append(elem); }

  E pop() {
    assert(_len > 0, "empty list");
    return _data[--_len];
  }

  void at_put(int i, const E& elem) {
    assert(0 <= i && i < _len, "illegal index");
    _data[i] = elem;
  }

  E at_grow(int i, const E& fill = E()) {
    assert(0 <= i, "negative index");
    check_nesting();
    if (i >= _len) {
      if (i >= _max) grow(i);
      for (int j = _len; j <= i; j++)
        _data[j] = fill;
      _len = i+1;
    }
    return _data[i];
  }

  void at_put_grow(int i, const E& elem, const E& fill = E()) {
    assert(0 <= i, "negative index");
    check_nesting();
    raw_at_put_grow(i, elem, fill);
  }

  bool contains(const E& elem) const {
    for (int i = 0; i < _len; i++) {
      if (_data[i] == elem) return true;
    }
    return false;
  }

  int  find(const E& elem) const {
    for (int i = 0; i < _len; i++) {
      if (_data[i] == elem) return i;
    }
    return -1;
  }

  int  find(void* token, bool f(void*, E)) const {
    for (int i = 0; i < _len; i++) {
      if (f(token, _data[i])) return i;
    }
    return -1;
  }

  int  find_at_end(void* token, bool f(void*, E)) const {
    // start at the end of the array
    for (int i = _len-1; i >= 0; i--) {
      if (f(token, _data[i])) return i;
    }
    return -1;
  }

  void remove(const E& elem) {
    for (int i = 0; i < _len; i++) {
      if (_data[i] == elem) {
        for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j];
        _len--;
        return;
      }
    }
    ShouldNotReachHere();
  }

  void remove_at(int index) {
    assert(0 <= index && index < _len, "illegal index");
    for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j];
    _len--;
  }

  // inserts the given element before the element at index i
  void insert_before(const int idx, const E& elem) {
    check_nesting();
    if (_len == _max) grow(_len);
    for (int j = _len - 1; j >= idx; j--) {
      _data[j + 1] = _data[j];
    }
    _len++;
    _data[idx] = elem;
  }

  void appendAll(const GrowableArray<E>* l) {
    for (int i = 0; i < l->_len; i++) {
      raw_at_put_grow(_len, l->_data[i], 0);
    }
  }

  void sort(int f(E*,E*)) {
    qsort(_data, length(), sizeof(E), (_sort_Fn)f);
  }
  // sort by fixed-stride sub arrays:
  void sort(int f(E*,E*), int stride) {
    qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
  }
};

// Global GrowableArray methods (one instance in the library per each 'E' type).

template<class E> void GrowableArray<E>::grow(int j) {
    // grow the array by doubling its size (amortized growth)
    int old_max = _max;
    if (_max == 0) _max = 1; // prevent endless loop
    while (j >= _max) _max = _max*2;
    // j < _max
    E* newData = (E*)raw_allocate(sizeof(E));
    int i = 0;
    for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
    for (     ; i < _max; i++) ::new ((void*)&newData[i]) E();
    for (i = 0; i < old_max; i++) _data[i].~E();
    if (on_C_heap() && _data != NULL) {
      FreeHeap(_data);
    }
    _data = newData;
}

template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
    if (i >= _len) {
      if (i >= _max) grow(i);
      for (int j = _len; j < i; j++)
        _data[j] = fill;
      _len = i+1;
    }
    _data[i] = p;
}

// This function clears and deallocate the data in the growable array that
// has been allocated on the C heap.  It's not public - called by the
// destructor.
template<class E> void GrowableArray<E>::clear_and_deallocate() {
    assert(on_C_heap(),
           "clear_and_deallocate should only be called when on C heap");
    clear();
    if (_data != NULL) {
      for (int i = 0; i < _max; i++) _data[i].~E();
      FreeHeap(_data);
      _data = NULL;
    }
}

template<class E> void GrowableArray<E>::print() {
    tty->print("Growable Array " INTPTR_FORMAT, this);
    tty->print(": length %ld (_max %ld) { ", _len, _max);
    for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
    tty->print("}\n");
}

#endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP