1/*
2 * Copyright 2009, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5#ifndef UNUSED_VNODES_H
6#define UNUSED_VNODES_H
7
8
9#include <algorithm>
10
11#include <util/AutoLock.h>
12#include <util/list.h>
13
14#include <low_resource_manager.h>
15
16#include "Vnode.h"
17
18
19const static uint32 kMaxUnusedVnodes = 8192;
20	// This is the maximum number of unused vnodes that the system
21	// will keep around (weak limit, if there is enough memory left,
22	// they won't get flushed even when hitting that limit).
23	// It may be chosen with respect to the available memory or enhanced
24	// by some timestamp/frequency heurism.
25
26
27/*!	\brief Guards sUnusedVnodeList and sUnusedVnodes.
28
29	Innermost lock. Must not be held when acquiring any other lock.
30*/
31static mutex sUnusedVnodesLock = MUTEX_INITIALIZER("unused vnodes");
32static list sUnusedVnodeList;
33static uint32 sUnusedVnodes = 0;
34
35static const int32 kMaxHotVnodes = 1024;
36static rw_lock sHotVnodesLock = RW_LOCK_INITIALIZER("hot vnodes");
37static Vnode* sHotVnodes[kMaxHotVnodes];
38static int32 sNextHotVnodeIndex = 0;
39
40static const int32 kUnusedVnodesCheckInterval = 64;
41static int32 sUnusedVnodesCheckCount = 0;
42
43
44/*!	Must be called with sHotVnodesLock write-locked.
45*/
46static void
47flush_hot_vnodes_locked()
48{
49	MutexLocker unusedLocker(sUnusedVnodesLock);
50
51	int32 count = std::min(sNextHotVnodeIndex, kMaxHotVnodes);
52	for (int32 i = 0; i < count; i++) {
53		Vnode* vnode = sHotVnodes[i];
54		if (vnode == NULL)
55			continue;
56
57		if (vnode->IsHot()) {
58			if (vnode->IsUnused()) {
59				list_add_item(&sUnusedVnodeList, vnode);
60				sUnusedVnodes++;
61			}
62			vnode->SetHot(false);
63		}
64
65		sHotVnodes[i] = NULL;
66	}
67
68	unusedLocker.Unlock();
69
70	sNextHotVnodeIndex = 0;
71}
72
73
74
75/*!	To be called when the vnode's ref count drops to 0.
76	Must be called with sVnodeLock at least read-locked and the vnode locked.
77	\param vnode The vnode.
78	\return \c true, if the caller should trigger unused vnode freeing.
79*/
80static bool
81vnode_unused(Vnode* vnode)
82{
83	ReadLocker hotReadLocker(sHotVnodesLock);
84
85	vnode->SetUnused(true);
86
87	bool result = false;
88	int32 checkCount = atomic_add(&sUnusedVnodesCheckCount, 1);
89	if (checkCount == kUnusedVnodesCheckInterval) {
90		uint32 unusedCount = atomic_get((int32*)&sUnusedVnodes);
91		if (unusedCount > kMaxUnusedVnodes
92			&& low_resource_state(
93				B_KERNEL_RESOURCE_PAGES | B_KERNEL_RESOURCE_MEMORY)
94					!= B_NO_LOW_RESOURCE) {
95			// there are too many unused vnodes -- tell the caller to free the
96			// oldest ones
97			result = true;
98		} else {
99			// nothing urgent -- reset the counter and re-check then
100			atomic_set(&sUnusedVnodesCheckCount, 0);
101		}
102	}
103
104	// nothing to do, if the node is already hot
105	if (vnode->IsHot())
106		return result;
107
108	// no -- enter it
109	int32 index = atomic_add(&sNextHotVnodeIndex, 1);
110	if (index < kMaxHotVnodes) {
111		vnode->SetHot(true);
112		sHotVnodes[index] = vnode;
113		return result;
114	}
115
116	// the array is full -- it has to be emptied
117	hotReadLocker.Unlock();
118	WriteLocker hotWriteLocker(sHotVnodesLock);
119
120	// unless someone was faster than we were, we have to flush the array
121	if (sNextHotVnodeIndex >= kMaxHotVnodes)
122		flush_hot_vnodes_locked();
123
124	// enter the vnode
125	index = sNextHotVnodeIndex++;
126	vnode->SetHot(true);
127	sHotVnodes[index] = vnode;
128
129	return result;
130}
131
132
133/*!	To be called when the vnode's ref count is changed from 0 to 1.
134	Must be called with sVnodeLock at least read-locked and the vnode locked.
135	\param vnode The vnode.
136*/
137static void
138vnode_used(Vnode* vnode)
139{
140	ReadLocker hotReadLocker(sHotVnodesLock);
141
142	if (!vnode->IsUnused())
143		return;
144
145	vnode->SetUnused(false);
146
147	if (!vnode->IsHot()) {
148		MutexLocker unusedLocker(sUnusedVnodesLock);
149		list_remove_item(&sUnusedVnodeList, vnode);
150		sUnusedVnodes--;
151	}
152}
153
154
155/*!	To be called when the vnode's is about to be freed.
156	Must be called with sVnodeLock at least read-locked and the vnode locked.
157	\param vnode The vnode.
158*/
159static void
160vnode_to_be_freed(Vnode* vnode)
161{
162	ReadLocker hotReadLocker(sHotVnodesLock);
163
164	if (vnode->IsHot()) {
165		// node is hot -- remove it from the array
166// TODO: Maybe better completely flush the array while at it?
167		int32 count = atomic_get(&sNextHotVnodeIndex);
168		count = std::min(count, kMaxHotVnodes);
169		for (int32 i = 0; i < count; i++) {
170			if (sHotVnodes[i] == vnode) {
171				sHotVnodes[i] = NULL;
172				break;
173			}
174		}
175	} else if (vnode->IsUnused()) {
176		MutexLocker unusedLocker(sUnusedVnodesLock);
177		list_remove_item(&sUnusedVnodeList, vnode);
178		sUnusedVnodes--;
179	}
180
181	vnode->SetUnused(false);
182}
183
184
185static inline void
186flush_hot_vnodes()
187{
188	WriteLocker hotWriteLocker(sHotVnodesLock);
189	flush_hot_vnodes_locked();
190}
191
192
193static inline void
194unused_vnodes_check_started()
195{
196	atomic_set(&sUnusedVnodesCheckCount, kUnusedVnodesCheckInterval + 1);
197}
198
199
200static inline void
201unused_vnodes_check_done()
202{
203	atomic_set(&sUnusedVnodesCheckCount, 0);
204}
205
206
207#endif	// UNUSED_VNODES_H
208