osfmk/vm/vm_purgeable.c

44 struct token {
50 struct token	*tokens;
55 token_idx_t     token_init_idx = 1;		/* token 0 is reserved!! */
57 						 * be added onto token queue */
59 int             available_for_purge = 0;	/* increase when ripe token
61 						 * token removed.
97 	token_idx_t     token = queue->token_q_head;
115 	while (token) {
116 		if (tokens[token].count != 0) {
119 				assert(token == queue->token_q_unripe);
120 				unripe = token;
122 			page_cnt += tokens[token].count;
124 		if (tokens[token].next == 0)
125 			assert(queue->token_q_tail == token);
128 		token = tokens[token].next;
135 	/* obsolete queue doesn't maintain token counts */
146  * Add a token. Allocate token queue memory if necessary.
156 	/* new token */
157 	token_idx_t     token;
163 		token = token_free_idx;
165 	} else if (token_init_idx < token_q_max_cnt) {	/* lazy token array init */
166 		token = token_init_idx;
188 		struct token *new_loc;
192 		if (alloc_size / sizeof (struct token) > TOKEN_COUNT_MAX) {
219 		struct token *old_tokens=tokens;
224 						 sizeof(struct token));
225 		assert (token_init_idx < token_q_max_cnt);	/* We must have a free token now */
241 	assert (token);
256 	/* set token counter value */
258 		tokens[token].count = queue->new_pages;
260 		tokens[token].count = 0;	/* all obsolete items are
264 	/* put token on token counter list */
265 	tokens[token].next = 0;
268 		queue->token_q_head = token;
269 		tokens[token].prev = 0;
271 		tokens[queue->token_q_tail].next = token;
272 		tokens[token].prev = queue->token_q_tail;
274 	if (queue->token_q_unripe == 0) {	/* only ripe tokens (token
276 		if (tokens[token].count > 0)
277 			queue->token_q_unripe = token;	/* first unripe token */
279 			available_for_purge++;	/* added a ripe token?
282 	queue->token_q_tail = token;
292 			      tokens[token].count,	/* num pages on token
293 							 * (last token) */
303  * Remove first token from queue and return its index. Add its count to the
304  * count of the next token.
314 	token_idx_t     token;
315 	token = queue->token_q_head;
317 	assert(token);
319 	if (token) {
323 			queue->token_q_unripe = tokens[token].next;
325 			/* we're removing a ripe token. decrease count */
331 			assert(tokens[token].next == 0);
333 		queue->token_q_head = tokens[token].next;
335 			tokens[queue->token_q_head].count += tokens[token].count;
341 			 * created token
343 			queue->new_pages += tokens[token].count;
355 										 * first token */
357 								 * next token */
362 	return token;
372 	token_idx_t     token;
373 	token = queue->token_q_tail;
375 	assert(token);
377 	if (token) {
381 			assert(tokens[token].next == 0);
384 			/* we're removing a ripe token. decrease count */
387 		} else if (queue->token_q_unripe == token) {
388 			/* we're removing the only unripe token */
392 		if (token == queue->token_q_head) {
393 			/* token is the last one in the queue */
399 			new_tail = tokens[token].prev;
402 			assert(tokens[new_tail].next == token);
408 		queue->new_pages += tokens[token].count;
417 										 * first token */
419 								 * next token */
424 	return token;
428  * Delete first token from queue. Return token to token queue.
437 	token_idx_t     token = vm_purgeable_token_remove_first(queue);
439 	if (token) {
440 		/* stick removed token on free queue */
441 		tokens[token].next = token_free_idx;
442 		tokens[token].prev = 0;
443 		token_free_idx = token;
453 	token_idx_t     token = vm_purgeable_token_remove_last(queue);
455 	if (token) {
456 		/* stick removed token on free queue */
457 		tokens[token].next = token_free_idx;
458 		tokens[token].prev = 0;
459 		token_free_idx = token;
488 	 * Decrement token counters. A token counter can be zero, this means the
516 											 * first token */
520 				continue;	/* One token ripened. Make sure to
524 				break;	/* Current token not ripe and no more pages.
546  * each volatile group. Select a queue with a ripe token.
549  *   Yes - purge it. Remove token.
552  *     Yes - purge it. Remove token. If there is no ripe token, remove ripe
553  *      token from other queue and migrate unripe token from this
564 	/* return token to free list. advance token list. */
584  * Delete a ripe token from the given queue. If there are no ripe tokens on
585  * that queue, delete a ripe token from queue2, and migrate an unripe token
598 		/* This queue has a ripe token. Remove. */
603 		 * queue2 must have a ripe token. Remove, and migrate one
607 		/* migrate unripe token */
608 		token_idx_t     token;
611 		/* remove token from queue1 */
614 		token = vm_purgeable_token_remove_first(queue);
615 		assert(token);
617 		count = tokens[token].count;
631 		/* should the inserted token become the first unripe token? */
633 			queue2->token_q_unripe = token;	/* if so, must update unripe pointer */
636 		 * insert token.
638 		 * otherwise, reduce counter of next token
641 		tokens[token].count = count;
646 			tokens[token].next = token_to_insert_before;
647 			tokens[token_to_insert_before].prev = token;
652 			/* if we ran off the end of the list, the token to insert after is the tail */
655 			tokens[token].next = 0;
656 			queue2->token_q_tail = token;
663 			tokens[token].prev = token_to_insert_after;
664 			tokens[token_to_insert_after].next = token;
667 			tokens[token].prev = 0;
668 			queue2->token_q_head = token;
711 			/* we want an object that has a ripe token */
802 		 * lock, remove a token and then purge the object.
868 	/* Need the page queue lock since we'll be changing the token queue. */
884 				/* no token: look at next purgeable queue */
889 				/* no ripe token: next queue */
898 		 * lock, remove a token and then purge the object.
937 				/* This is the token migration case, and it works between
1379 			/* remove a token */