From 09041a4eda3be3cda7644e7b28b48390ea4b4836 Mon Sep 17 00:00:00 2001 From: "barraclough@apple.com" Date: Mon, 23 Jan 2012 23:30:57 +0000 Subject: [PATCH] https://bugs.webkit.org/show_bug.cgi?id=76855 Implement a JIT-code aware sampling profiler for JSC Reviewed by Geoff Garen. Step 2: generalize RedBlackTree. The profiler is going to want tio use a RedBlackTree, allow this class to work with subclasses of RedBlackTree::Node, Node should not need to know the names of the m_key and m_value fields (the subclass can provide a key() accessor), and RedBlackTree does not need to know anything about ValueType. * JavaScriptCore.exp: * wtf/MetaAllocator.cpp: (WTF::MetaAllocator::findAndRemoveFreeSpace): (WTF::MetaAllocator::debugFreeSpaceSize): (WTF::MetaAllocator::addFreeSpace): * wtf/MetaAllocator.h: (WTF::MetaAllocator::FreeSpaceNode::FreeSpaceNode): (WTF::MetaAllocator::FreeSpaceNode::key): * wtf/MetaAllocatorHandle.h: (WTF::MetaAllocatorHandle::key): * wtf/RedBlackTree.h: (WTF::RedBlackTree::Node::successor): (WTF::RedBlackTree::Node::predecessor): (WTF::RedBlackTree::Node::parent): (WTF::RedBlackTree::Node::setParent): (WTF::RedBlackTree::Node::left): (WTF::RedBlackTree::Node::setLeft): (WTF::RedBlackTree::Node::right): (WTF::RedBlackTree::Node::setRight): (WTF::RedBlackTree::insert): (WTF::RedBlackTree::remove): (WTF::RedBlackTree::findExact): (WTF::RedBlackTree::findLeastGreaterThanOrEqual): (WTF::RedBlackTree::findGreatestLessThanOrEqual): (WTF::RedBlackTree::first): (WTF::RedBlackTree::last): (WTF::RedBlackTree::size): (WTF::RedBlackTree::treeMinimum): (WTF::RedBlackTree::treeMaximum): (WTF::RedBlackTree::treeInsert): (WTF::RedBlackTree::leftRotate): (WTF::RedBlackTree::rightRotate): (WTF::RedBlackTree::removeFixup): git-svn-id: http://svn.webkit.org/repository/webkit/trunk@105646 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- Source/JavaScriptCore/ChangeLog | 47 ++++++++++ Source/JavaScriptCore/JavaScriptCore.exp | 1 - Source/JavaScriptCore/wtf/MetaAllocator.cpp | 60 ++++++------- Source/JavaScriptCore/wtf/MetaAllocator.h | 23 ++++- Source/JavaScriptCore/wtf/RedBlackTree.h | 135 +++++++++++++--------------- 5 files changed, 159 insertions(+), 107 deletions(-) diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog index 2c5098a..cdc050f 100644 --- a/Source/JavaScriptCore/ChangeLog +++ b/Source/JavaScriptCore/ChangeLog @@ -1,3 +1,50 @@ +2012-01-23 Gavin Barraclough + + https://bugs.webkit.org/show_bug.cgi?id=76855 + Implement a JIT-code aware sampling profiler for JSC + + Reviewed by Geoff Garen. + + Step 2: generalize RedBlackTree. The profiler is going to want tio use + a RedBlackTree, allow this class to work with subclasses of + RedBlackTree::Node, Node should not need to know the names of the m_key + and m_value fields (the subclass can provide a key() accessor), and + RedBlackTree does not need to know anything about ValueType. + + * JavaScriptCore.exp: + * wtf/MetaAllocator.cpp: + (WTF::MetaAllocator::findAndRemoveFreeSpace): + (WTF::MetaAllocator::debugFreeSpaceSize): + (WTF::MetaAllocator::addFreeSpace): + * wtf/MetaAllocator.h: + (WTF::MetaAllocator::FreeSpaceNode::FreeSpaceNode): + (WTF::MetaAllocator::FreeSpaceNode::key): + * wtf/MetaAllocatorHandle.h: + (WTF::MetaAllocatorHandle::key): + * wtf/RedBlackTree.h: + (WTF::RedBlackTree::Node::successor): + (WTF::RedBlackTree::Node::predecessor): + (WTF::RedBlackTree::Node::parent): + (WTF::RedBlackTree::Node::setParent): + (WTF::RedBlackTree::Node::left): + (WTF::RedBlackTree::Node::setLeft): + (WTF::RedBlackTree::Node::right): + (WTF::RedBlackTree::Node::setRight): + (WTF::RedBlackTree::insert): + (WTF::RedBlackTree::remove): + (WTF::RedBlackTree::findExact): + (WTF::RedBlackTree::findLeastGreaterThanOrEqual): + (WTF::RedBlackTree::findGreatestLessThanOrEqual): + (WTF::RedBlackTree::first): + (WTF::RedBlackTree::last): + (WTF::RedBlackTree::size): + (WTF::RedBlackTree::treeMinimum): + (WTF::RedBlackTree::treeMaximum): + (WTF::RedBlackTree::treeInsert): + (WTF::RedBlackTree::leftRotate): + (WTF::RedBlackTree::rightRotate): + (WTF::RedBlackTree::removeFixup): + 2012-01-23 Andy Estes Fix the build after r105635. diff --git a/Source/JavaScriptCore/JavaScriptCore.exp b/Source/JavaScriptCore/JavaScriptCore.exp index d09dc61d..9bcdaed 100644 --- a/Source/JavaScriptCore/JavaScriptCore.exp +++ b/Source/JavaScriptCore/JavaScriptCore.exp @@ -412,7 +412,6 @@ __ZN3WTF12detachThreadEj __ZN3WTF12isMainThreadEv __ZN3WTF12randomNumberEv __ZN3WTF13MetaAllocator17addFreshFreeSpaceEPvm -__ZN3WTF13MetaAllocator17freeFreeSpaceNodeEPNS_12RedBlackTreeImPvE4NodeE __ZN3WTF13MetaAllocator18debugFreeSpaceSizeEv __ZN3WTF13MetaAllocator8allocateEm __ZN3WTF13MetaAllocatorC2Em diff --git a/Source/JavaScriptCore/wtf/MetaAllocator.cpp b/Source/JavaScriptCore/wtf/MetaAllocator.cpp index 92205a5..99e6d06 100644 --- a/Source/JavaScriptCore/wtf/MetaAllocator.cpp +++ b/Source/JavaScriptCore/wtf/MetaAllocator.cpp @@ -178,18 +178,18 @@ void* MetaAllocator::findAndRemoveFreeSpace(size_t sizeInBytes) if (!node) return 0; - ASSERT(node->m_key >= sizeInBytes); + ASSERT(node->m_sizeInBytes >= sizeInBytes); m_freeSpaceSizeMap.remove(node); void* result; - if (node->m_key == sizeInBytes) { + if (node->m_sizeInBytes == sizeInBytes) { // Easy case: perfect fit, so just remove the node entirely. - result = node->m_value; + result = node->m_start; - m_freeSpaceStartAddressMap.remove(node->m_value); - m_freeSpaceEndAddressMap.remove(reinterpret_cast(reinterpret_cast(node->m_value) + node->m_key)); + m_freeSpaceStartAddressMap.remove(node->m_start); + m_freeSpaceEndAddressMap.remove(reinterpret_cast(reinterpret_cast(node->m_start) + node->m_sizeInBytes)); freeFreeSpaceNode(node); } else { // Try to be a good citizen and ensure that the returned chunk of memory @@ -199,31 +199,31 @@ void* MetaAllocator::findAndRemoveFreeSpace(size_t sizeInBytes) // of committed pages, since in the long run, smaller fragmentation means // fewer committed pages and fewer failures in general. - uintptr_t firstPage = reinterpret_cast(node->m_value) >> m_logPageSize; - uintptr_t lastPage = (reinterpret_cast(node->m_value) + node->m_key - 1) >> m_logPageSize; + uintptr_t firstPage = reinterpret_cast(node->m_start) >> m_logPageSize; + uintptr_t lastPage = (reinterpret_cast(node->m_start) + node->m_sizeInBytes - 1) >> m_logPageSize; - uintptr_t lastPageForLeftAllocation = (reinterpret_cast(node->m_value) + sizeInBytes - 1) >> m_logPageSize; - uintptr_t firstPageForRightAllocation = (reinterpret_cast(node->m_value) + node->m_key - sizeInBytes) >> m_logPageSize; + uintptr_t lastPageForLeftAllocation = (reinterpret_cast(node->m_start) + sizeInBytes - 1) >> m_logPageSize; + uintptr_t firstPageForRightAllocation = (reinterpret_cast(node->m_start) + node->m_sizeInBytes - sizeInBytes) >> m_logPageSize; if (lastPageForLeftAllocation - firstPage + 1 <= lastPage - firstPageForRightAllocation + 1) { // Allocate in the left side of the returned chunk, and slide the node to the right. - result = node->m_value; + result = node->m_start; - m_freeSpaceStartAddressMap.remove(node->m_value); + m_freeSpaceStartAddressMap.remove(node->m_start); - node->m_key -= sizeInBytes; - node->m_value = reinterpret_cast(reinterpret_cast(node->m_value) + sizeInBytes); + node->m_sizeInBytes -= sizeInBytes; + node->m_start = reinterpret_cast(reinterpret_cast(node->m_start) + sizeInBytes); m_freeSpaceSizeMap.insert(node); - m_freeSpaceStartAddressMap.add(node->m_value, node); + m_freeSpaceStartAddressMap.add(node->m_start, node); } else { // Allocate in the right size of the returned chunk, and slide the node to the left; - result = reinterpret_cast(reinterpret_cast(node->m_value) + node->m_key - sizeInBytes); + result = reinterpret_cast(reinterpret_cast(node->m_start) + node->m_sizeInBytes - sizeInBytes); - m_freeSpaceEndAddressMap.remove(reinterpret_cast(reinterpret_cast(node->m_value) + node->m_key)); + m_freeSpaceEndAddressMap.remove(reinterpret_cast(reinterpret_cast(node->m_start) + node->m_sizeInBytes)); - node->m_key -= sizeInBytes; + node->m_sizeInBytes -= sizeInBytes; m_freeSpaceSizeMap.insert(node); m_freeSpaceEndAddressMap.add(result, node); @@ -255,7 +255,7 @@ size_t MetaAllocator::debugFreeSpaceSize() SpinLockHolder locker(&m_lock); size_t result = 0; for (FreeSpaceNode* node = m_freeSpaceSizeMap.first(); node; node = node->successor()) - result += node->m_key; + result += node->m_sizeInBytes; return result; #else CRASH(); @@ -274,12 +274,12 @@ void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes) // We have something we can coalesce with on the left. Remove it from the tree, and // remove its end from the end address map. - ASSERT(reinterpret_cast(reinterpret_cast(leftNeighbor->second->m_value) + leftNeighbor->second->m_key) == leftNeighbor->first); + ASSERT(reinterpret_cast(reinterpret_cast(leftNeighbor->second->m_start) + leftNeighbor->second->m_sizeInBytes) == leftNeighbor->first); FreeSpaceNode* leftNode = leftNeighbor->second; - void* leftStart = leftNode->m_value; - size_t leftSize = leftNode->m_key; + void* leftStart = leftNode->m_start; + size_t leftSize = leftNode->m_sizeInBytes; void* leftEnd = reinterpret_cast(reinterpret_cast(leftStart) + leftSize); ASSERT(leftEnd == start); @@ -292,11 +292,11 @@ void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes) // Freeing something in the middle of free blocks. Coalesce both left and // right, whilst removing the right neighbor from the maps. - ASSERT(rightNeighbor->second->m_value == rightNeighbor->first); + ASSERT(rightNeighbor->second->m_start == rightNeighbor->first); FreeSpaceNode* rightNode = rightNeighbor->second; void* rightStart = rightNeighbor->first; - size_t rightSize = rightNode->m_key; + size_t rightSize = rightNode->m_sizeInBytes; void* rightEnd = reinterpret_cast(reinterpret_cast(rightStart) + rightSize); ASSERT(rightStart == end); @@ -308,12 +308,12 @@ void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes) freeFreeSpaceNode(rightNode); - leftNode->m_key += sizeInBytes + rightSize; + leftNode->m_sizeInBytes += sizeInBytes + rightSize; m_freeSpaceSizeMap.insert(leftNode); m_freeSpaceEndAddressMap.add(rightEnd, leftNode); } else { - leftNode->m_key += sizeInBytes; + leftNode->m_sizeInBytes += sizeInBytes; m_freeSpaceSizeMap.insert(leftNode); m_freeSpaceEndAddressMap.add(end, leftNode); @@ -324,7 +324,7 @@ void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes) if (rightNeighbor != m_freeSpaceStartAddressMap.end()) { FreeSpaceNode* rightNode = rightNeighbor->second; void* rightStart = rightNeighbor->first; - size_t rightSize = rightNode->m_key; + size_t rightSize = rightNode->m_sizeInBytes; void* rightEnd = reinterpret_cast(reinterpret_cast(rightStart) + rightSize); ASSERT(rightStart == end); @@ -333,8 +333,8 @@ void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes) m_freeSpaceSizeMap.remove(rightNode); m_freeSpaceStartAddressMap.remove(rightStart); - rightNode->m_key += sizeInBytes; - rightNode->m_value = start; + rightNode->m_sizeInBytes += sizeInBytes; + rightNode->m_start = start; m_freeSpaceSizeMap.insert(rightNode); m_freeSpaceStartAddressMap.add(start, rightNode); @@ -343,8 +343,8 @@ void MetaAllocator::addFreeSpace(void* start, size_t sizeInBytes) FreeSpaceNode* node = allocFreeSpaceNode(); - node->m_key = sizeInBytes; - node->m_value = start; + node->m_sizeInBytes = sizeInBytes; + node->m_start = start; m_freeSpaceSizeMap.insert(node); m_freeSpaceStartAddressMap.add(start, node); diff --git a/Source/JavaScriptCore/wtf/MetaAllocator.h b/Source/JavaScriptCore/wtf/MetaAllocator.h index a337039..b92ee9b 100644 --- a/Source/JavaScriptCore/wtf/MetaAllocator.h +++ b/Source/JavaScriptCore/wtf/MetaAllocator.h @@ -45,8 +45,8 @@ namespace WTF { class MetaAllocator { WTF_MAKE_NONCOPYABLE(MetaAllocator); + public: - WTF_EXPORT_PRIVATE MetaAllocator(size_t allocationGranule); virtual ~MetaAllocator(); @@ -101,8 +101,23 @@ private: friend class MetaAllocatorHandle; - typedef RedBlackTree Tree; - typedef Tree::Node FreeSpaceNode; + class FreeSpaceNode : public RedBlackTree::Node { + public: + FreeSpaceNode(void* start, size_t sizeInBytes) + : m_start(start) + , m_sizeInBytes(sizeInBytes) + { + } + + size_t key() + { + return m_sizeInBytes; + } + + void* m_start; + size_t m_sizeInBytes; + }; + typedef RedBlackTree Tree; // Remove free space from the allocator. This is effectively // the allocate() function, except that it does not mark the @@ -121,7 +136,7 @@ private: void incrementPageOccupancy(void* address, size_t sizeInBytes); void decrementPageOccupancy(void* address, size_t sizeInBytes); - + // Utilities. size_t roundUp(size_t sizeInBytes); diff --git a/Source/JavaScriptCore/wtf/RedBlackTree.h b/Source/JavaScriptCore/wtf/RedBlackTree.h index af4e5c8..19460c1 100644 --- a/Source/JavaScriptCore/wtf/RedBlackTree.h +++ b/Source/JavaScriptCore/wtf/RedBlackTree.h @@ -41,7 +41,7 @@ namespace WTF { // reference to this node. // - The key type must implement operator< and ==. -template +template class RedBlackTree { WTF_MAKE_NONCOPYABLE(RedBlackTree); private: @@ -55,18 +55,12 @@ public: friend class RedBlackTree; public: - Node(KeyType key, ValueType value) - : m_key(key) - , m_value(value) - { - } - - const Node* successor() const + const NodeType* successor() const { const Node* x = this; if (x->right()) return treeMinimum(x->right()); - const Node* y = x->parent(); + const NodeType* y = x->parent(); while (y && x == y->right()) { x = y; y = y->parent(); @@ -74,12 +68,12 @@ public: return y; } - const Node* predecessor() const + const NodeType* predecessor() const { const Node* x = this; if (x->left()) return treeMaximum(x->left()); - const Node* y = x->parent(); + const NodeType* y = x->parent(); while (y && x == y->left()) { x = y; y = y->parent(); @@ -87,18 +81,15 @@ public: return y; } - Node* successor() + NodeType* successor() { - return const_cast(const_cast(this)->successor()); + return const_cast(const_cast(this)->successor()); } - - Node* predecessor() + + NodeType* predecessor() { - return const_cast(const_cast(this)->predecessor()); + return const_cast(const_cast(this)->predecessor()); } - - KeyType m_key; - ValueType m_value; private: void reset() @@ -110,32 +101,32 @@ public: // NOTE: these methods should pack the parent and red into a single // word. But doing so appears to reveal a bug in the compiler. - Node* parent() const + NodeType* parent() const { - return reinterpret_cast(m_parentAndRed & ~static_cast(1)); + return reinterpret_cast(m_parentAndRed & ~static_cast(1)); } - void setParent(Node* newParent) + void setParent(NodeType* newParent) { m_parentAndRed = reinterpret_cast(newParent) | (m_parentAndRed & 1); } - Node* left() const + NodeType* left() const { return m_left; } - void setLeft(Node* node) + void setLeft(NodeType* node) { m_left = node; } - Node* right() const + NodeType* right() const { return m_right; } - void setRight(Node* node) + void setRight(NodeType* node) { m_right = node; } @@ -155,17 +146,17 @@ public: m_parentAndRed &= ~static_cast(1); } - Node* m_left; - Node* m_right; + NodeType* m_left; + NodeType* m_right; uintptr_t m_parentAndRed; }; - + RedBlackTree() : m_root(0) { } - void insert(Node* x) + void insert(NodeType* x) { x->reset(); treeInsert(x); @@ -173,7 +164,7 @@ public: while (x != m_root && x->parent()->color() == Red) { if (x->parent() == x->parent()->parent()->left()) { - Node* y = x->parent()->parent()->right(); + NodeType* y = x->parent()->parent()->right(); if (y && y->color() == Red) { // Case 1 x->parent()->setColor(Black); @@ -193,7 +184,7 @@ public: } } else { // Same as "then" clause with "right" and "left" exchanged. - Node* y = x->parent()->parent()->left(); + NodeType* y = x->parent()->parent()->left(); if (y && y->color() == Red) { // Case 1 x->parent()->setColor(Black); @@ -217,20 +208,20 @@ public: m_root->setColor(Black); } - Node* remove(Node* z) + NodeType* remove(NodeType* z) { ASSERT(z); ASSERT(z->parent() || z == m_root); // Y is the node to be unlinked from the tree. - Node* y; + NodeType* y; if (!z->left() || !z->right()) y = z; else y = z->successor(); // Y is guaranteed to be non-null at this point. - Node* x; + NodeType* x; if (y->left()) x = y->left(); else @@ -238,7 +229,7 @@ public: // X is the child of y which might potentially replace y in // the tree. X might be null at this point. - Node* xParent; + NodeType* xParent; if (x) { x->setParent(y->parent()); xParent = x->parent(); @@ -281,20 +272,20 @@ public: return z; } - Node* remove(const KeyType& key) + NodeType* remove(const KeyType& key) { - Node* result = findExact(key); + NodeType* result = findExact(key); if (!result) return 0; return remove(result); } - Node* findExact(const KeyType& key) const + NodeType* findExact(const KeyType& key) const { - for (Node* current = m_root; current;) { - if (current->m_key == key) + for (NodeType* current = m_root; current;) { + if (current->key() == key) return current; - if (key < current->m_key) + if (key < current->key()) current = current->left(); else current = current->right(); @@ -302,13 +293,13 @@ public: return 0; } - Node* findLeastGreaterThanOrEqual(const KeyType& key) const + NodeType* findLeastGreaterThanOrEqual(const KeyType& key) const { - Node* best = 0; - for (Node* current = m_root; current;) { - if (current->m_key == key) + NodeType* best = 0; + for (NodeType* current = m_root; current;) { + if (current->key() == key) return current; - if (current->m_key < key) + if (current->key() < key) current = current->right(); else { best = current; @@ -318,13 +309,13 @@ public: return best; } - Node* findGreatestLessThanOrEqual(const KeyType& key) const + NodeType* findGreatestLessThanOrEqual(const KeyType& key) const { - Node* best = 0; - for (Node* current = m_root; current;) { - if (current->m_key == key) + NodeType* best = 0; + for (NodeType* current = m_root; current;) { + if (current->key() == key) return current; - if (current->m_key > key) + if (current->key() > key) current = current->left(); else { best = current; @@ -334,14 +325,14 @@ public: return best; } - Node* first() const + NodeType* first() const { if (!m_root) return 0; return treeMinimum(m_root); } - Node* last() const + NodeType* last() const { if (!m_root) return 0; @@ -352,7 +343,7 @@ public: size_t size() { size_t result = 0; - for (Node* current = first(); current; current = current->successor()) + for (NodeType* current = first(); current; current = current->successor()) result++; return result; } @@ -366,46 +357,46 @@ public: private: // Finds the minimum element in the sub-tree rooted at the given // node. - static Node* treeMinimum(Node* x) + static NodeType* treeMinimum(NodeType* x) { while (x->left()) x = x->left(); return x; } - static Node* treeMaximum(Node* x) + static NodeType* treeMaximum(NodeType* x) { while (x->right()) x = x->right(); return x; } - static const Node* treeMinimum(const Node* x) + static const NodeType* treeMinimum(const NodeType* x) { while (x->left()) x = x->left(); return x; } - static const Node* treeMaximum(const Node* x) + static const NodeType* treeMaximum(const NodeType* x) { while (x->right()) x = x->right(); return x; } - void treeInsert(Node* z) + void treeInsert(NodeType* z) { ASSERT(!z->left()); ASSERT(!z->right()); ASSERT(!z->parent()); ASSERT(z->color() == Red); - Node* y = 0; - Node* x = m_root; + NodeType* y = 0; + NodeType* x = m_root; while (x) { y = x; - if (z->m_key < x->m_key) + if (z->key() < x->key()) x = x->left(); else x = x->right(); @@ -414,7 +405,7 @@ private: if (!y) m_root = z; else { - if (z->m_key < y->m_key) + if (z->key() < y->key()) y->setLeft(z); else y->setRight(z); @@ -427,10 +418,10 @@ private: // Left-rotates the subtree rooted at x. // Returns the new root of the subtree (x's right child). - Node* leftRotate(Node* x) + NodeType* leftRotate(NodeType* x) { // Set y. - Node* y = x->right(); + NodeType* y = x->right(); // Turn y's left subtree into x's right subtree. x->setRight(y->left()); @@ -457,10 +448,10 @@ private: // Right-rotates the subtree rooted at y. // Returns the new root of the subtree (y's left child). - Node* rightRotate(Node* y) + NodeType* rightRotate(NodeType* y) { // Set x. - Node* x = y->left(); + NodeType* x = y->left(); // Turn x's right subtree into y's left subtree. y->setLeft(x->right()); @@ -488,7 +479,7 @@ private: // Restores the red-black property to the tree after splicing out // a node. Note that x may be null, which is why xParent must be // supplied. - void removeFixup(Node* x, Node* xParent) + void removeFixup(NodeType* x, NodeType* xParent) { while (x != m_root && (!x || x->color() == Black)) { if (x == xParent->left()) { @@ -496,7 +487,7 @@ private: // The reason is not obvious from simply looking at // the code; it comes about from the properties of the // red-black tree. - Node* w = xParent->right(); + NodeType* w = xParent->right(); ASSERT(w); // x's sibling should not be null. if (w->color() == Red) { // Case 1 @@ -536,7 +527,7 @@ private: // The reason is not obvious from simply looking at // the code; it comes about from the properties of the // red-black tree. - Node* w = xParent->left(); + NodeType* w = xParent->left(); ASSERT(w); // x's sibling should not be null. if (w->color() == Red) { // Case 1 @@ -574,7 +565,7 @@ private: x->setColor(Black); } - Node* m_root; + NodeType* m_root; }; } -- 2.7.4