Mercurial > hg > truffle
view src/share/vm/utilities/linkedlist.hpp @ 20543:e7d0505c8a30
8059758: Footprint regressions with JDK-8038423
Summary: Changes in JDK-8038423 always initialize (zero out) virtual memory used for auxiliary data structures. This causes a footprint regression for G1 in startup benchmarks. This is because they do not touch that memory at all, so the operating system does not actually commit these pages. The fix is to, if the initialization value of the data structures matches the default value of just committed memory (=0), do not do anything.
Reviewed-by: jwilhelm, brutisso
author | tschatzl |
---|---|
date | Fri, 10 Oct 2014 15:51:58 +0200 |
parents | 833b0f92429a |
children |
line wrap: on
line source
/* * Copyright (c) 2014, 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_LINKED_LIST_HPP #define SHARE_VM_UTILITIES_LINKED_LIST_HPP #include "memory/allocation.hpp" /* * The implementation of a generic linked list, which uses various * backing storages, such as C heap, arena and resource, etc. */ // An entry in a linked list. It should use the same backing storage // as the linked list that contains this entry. template <class E> class LinkedListNode : public ResourceObj { private: E _data; // embedded content LinkedListNode<E>* _next; // next entry protected: LinkedListNode() : _next(NULL) { } public: LinkedListNode(const E& e): _data(e), _next(NULL) { } inline void set_next(LinkedListNode<E>* node) { _next = node; } inline LinkedListNode<E> * next() const { return _next; } E* data() { return &_data; } const E* peek() const { return &_data; } }; // A linked list interface. It does not specify // any storage type it uses, so all methods involving // memory allocation or deallocation are pure virtual template <class E> class LinkedList : public ResourceObj { protected: LinkedListNode<E>* _head; public: LinkedList() : _head(NULL) { } inline void set_head(LinkedListNode<E>* h) { _head = h; } inline LinkedListNode<E>* head() const { return _head; } inline bool is_empty() const { return head() == NULL; } inline size_t size() const { LinkedListNode<E>* p; size_t count = 0; for (p = head(); p != NULL; count++, p = p->next()); return count; } // Move all entries from specified linked list to this one virtual void move(LinkedList<E>* list) = 0; // Add an entry to this linked list virtual LinkedListNode<E>* add(const E& e) = 0; // Add all entries from specified linked list to this one, virtual void add(LinkedListNode<E>* node) = 0; // Add a linked list to this linked list virtual bool add(const LinkedList<E>* list) = 0; // Search entry in the linked list virtual LinkedListNode<E>* find_node(const E& e) = 0; virtual E* find(const E& e) = 0; // Insert entry to the linked list virtual LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref) = 0; virtual LinkedListNode<E>* insert_after (const E& e, LinkedListNode<E>* ref) = 0; // Remove entry from the linked list virtual bool remove(const E& e) = 0; virtual bool remove(LinkedListNode<E>* node) = 0; virtual bool remove_before(LinkedListNode<E>* ref) = 0; virtual bool remove_after(LinkedListNode<E>* ref) = 0; LinkedListNode<E>* unlink_head() { LinkedListNode<E>* h = this->head(); if (h != NULL) { this->set_head(h->next()); } return h; } DEBUG_ONLY(virtual ResourceObj::allocation_type storage_type() = 0;) }; // A linked list implementation. // The linked list can be allocated in various type of memory: C heap, arena and resource area, etc. template <class E, ResourceObj::allocation_type T = ResourceObj::C_HEAP, MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL> class LinkedListImpl : public LinkedList<E> { protected: Arena* _arena; public: LinkedListImpl() : _arena(NULL) { } LinkedListImpl(Arena* a) : _arena(a) { } virtual ~LinkedListImpl() { clear(); } virtual void clear() { LinkedListNode<E>* p = this->head(); this->set_head(NULL); while (p != NULL) { LinkedListNode<E>* to_delete = p; p = p->next(); delete_node(to_delete); } } // Add an entry to the linked list virtual LinkedListNode<E>* add(const E& e) { LinkedListNode<E>* node = this->new_node(e); if (node != NULL) { this->add(node); } return node; } virtual void add(LinkedListNode<E>* node) { assert(node != NULL, "NULL pointer"); node->set_next(this->head()); this->set_head(node); } // Move a linked list to this linked list, both have to be allocated on the same // storage type. virtual void move(LinkedList<E>* list) { assert(list->storage_type() == this->storage_type(), "Different storage type"); LinkedListNode<E>* node = this->head(); while (node != NULL && node->next() != NULL) { node = node->next(); } if (node == NULL) { this->set_head(list->head()); } else { node->set_next(list->head()); } // All entries are moved list->set_head(NULL); } virtual bool add(const LinkedList<E>* list) { LinkedListNode<E>* node = list->head(); while (node != NULL) { if (this->add(*node->peek()) == NULL) { return false; } node = node->next(); } return true; } virtual LinkedListNode<E>* find_node(const E& e) { LinkedListNode<E>* p = this->head(); while (p != NULL && !p->peek()->equals(e)) { p = p->next(); } return p; } E* find(const E& e) { LinkedListNode<E>* node = find_node(e); return (node == NULL) ? NULL : node->data(); } // Add an entry in front of the reference entry LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref_node) { LinkedListNode<E>* node = this->new_node(e); if (node == NULL) return NULL; if (ref_node == this->head()) { node->set_next(ref_node); this->set_head(node); } else { LinkedListNode<E>* p = this->head(); while (p != NULL && p->next() != ref_node) { p = p->next(); } assert(p != NULL, "ref_node not in the list"); node->set_next(ref_node); p->set_next(node); } return node; } // Add an entry behind the reference entry LinkedListNode<E>* insert_after(const E& e, LinkedListNode<E>* ref_node) { LinkedListNode<E>* node = this->new_node(e); if (node == NULL) return NULL; node->set_next(ref_node->next()); ref_node->set_next(node); return node; } // Remove an entry from the linked list. // Return true if the entry is successfully removed virtual bool remove(const E& e) { LinkedListNode<E>* tmp = this->head(); LinkedListNode<E>* prev = NULL; while (tmp != NULL) { if (tmp->peek()->equals(e)) { return remove_after(prev); } prev = tmp; tmp = tmp->next(); } return false; } // Remove the node after the reference entry virtual bool remove_after(LinkedListNode<E>* prev) { LinkedListNode<E>* to_delete; if (prev == NULL) { to_delete = this->unlink_head(); } else { to_delete = prev->next(); if (to_delete != NULL) { prev->set_next(to_delete->next()); } } if (to_delete != NULL) { delete_node(to_delete); return true; } return false; } virtual bool remove(LinkedListNode<E>* node) { LinkedListNode<E>* p = this->head(); while (p != NULL && p->next() != node) { p = p->next(); } if (p != NULL) { p->set_next(node->next()); delete_node(node); return true; } else { return false; } } virtual bool remove_before(LinkedListNode<E>* ref) { assert(ref != NULL, "NULL pointer"); LinkedListNode<E>* p = this->head(); LinkedListNode<E>* to_delete = NULL; // to be deleted LinkedListNode<E>* prev = NULL; // node before the node to be deleted while (p != NULL && p != ref) { prev = to_delete; to_delete = p; p = p->next(); } if (p == NULL || to_delete == NULL) return false; assert(to_delete->next() == ref, "Wrong node to delete"); assert(prev == NULL || prev->next() == to_delete, "Sanity check"); if (prev == NULL) { assert(to_delete == this->head(), "Must be head"); this->set_head(to_delete->next()); } else { prev->set_next(to_delete->next()); } delete_node(to_delete); return true; } DEBUG_ONLY(ResourceObj::allocation_type storage_type() { return T; }) protected: // Create new linked list node object in specified storage LinkedListNode<E>* new_node(const E& e) const { switch(T) { case ResourceObj::ARENA: { assert(_arena != NULL, "Arena not set"); return new(_arena) LinkedListNode<E>(e); } case ResourceObj::RESOURCE_AREA: case ResourceObj::C_HEAP: { if (alloc_failmode == AllocFailStrategy::RETURN_NULL) { return new(std::nothrow, T, F) LinkedListNode<E>(e); } else { return new(T, F) LinkedListNode<E>(e); } } default: ShouldNotReachHere(); } return NULL; } // Delete linked list node object void delete_node(LinkedListNode<E>* node) { if (T == ResourceObj::C_HEAP) { delete node; } } }; // Sorted linked list. The linked list maintains sorting order specified by the comparison // function template <class E, int (*FUNC)(const E&, const E&), ResourceObj::allocation_type T = ResourceObj::C_HEAP, MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL> class SortedLinkedList : public LinkedListImpl<E, T, F, alloc_failmode> { public: SortedLinkedList() { } SortedLinkedList(Arena* a) : LinkedListImpl<E, T, F, alloc_failmode>(a) { } virtual LinkedListNode<E>* add(const E& e) { return LinkedListImpl<E, T, F, alloc_failmode>::add(e); } virtual void move(LinkedList<E>* list) { assert(list->storage_type() == this->storage_type(), "Different storage type"); LinkedListNode<E>* node; while ((node = list->unlink_head()) != NULL) { this->add(node); } assert(list->is_empty(), "All entries are moved"); } virtual void add(LinkedListNode<E>* node) { assert(node != NULL, "NULL pointer"); LinkedListNode<E>* tmp = this->head(); LinkedListNode<E>* prev = NULL; int cmp_val; while (tmp != NULL) { cmp_val = FUNC(*tmp->peek(), *node->peek()); if (cmp_val >= 0) { break; } prev = tmp; tmp = tmp->next(); } if (prev != NULL) { node->set_next(prev->next()); prev->set_next(node); } else { node->set_next(this->head()); this->set_head(node); } } virtual bool add(const LinkedList<E>* list) { return LinkedListImpl<E, T, F, alloc_failmode>::add(list); } virtual LinkedListNode<E>* find_node(const E& e) { LinkedListNode<E>* p = this->head(); while (p != NULL) { int comp_val = FUNC(*p->peek(), e); if (comp_val == 0) { return p; } else if (comp_val > 0) { return NULL; } p = p->next(); } return NULL; } }; // Iterates all entries in the list template <class E> class LinkedListIterator : public StackObj { private: LinkedListNode<E>* _p; bool _is_empty; public: LinkedListIterator(LinkedListNode<E>* head) : _p(head) { _is_empty = (head == NULL); } bool is_empty() const { return _is_empty; } const E* next() { if (_p == NULL) return NULL; const E* e = _p->peek(); _p = _p->next(); return e; } }; #endif