1/* $NetBSD: uvm_page_array.c,v 1.9 2020/05/26 21:52:12 ad Exp $ */ 2 3/*- 4 * Copyright (c)2011 YAMAMOTO Takashi, 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29#include <sys/cdefs.h> 30__KERNEL_RCSID(0, "$NetBSD: uvm_page_array.c,v 1.9 2020/05/26 21:52:12 ad Exp $"); 31 32#include <sys/param.h> 33#include <sys/systm.h> 34 35#include <uvm/uvm_extern.h> 36#include <uvm/uvm_object.h> 37#include <uvm/uvm_page.h> 38#include <uvm/uvm_page_array.h> 39 40/* 41 * uvm_page_array_init: initialize the array. 42 */ 43 44void 45uvm_page_array_init(struct uvm_page_array *ar, struct uvm_object *uobj, 46 unsigned int flags) 47{ 48 49 ar->ar_idx = 0; 50 ar->ar_npages = 0; 51 ar->ar_uobj = uobj; 52 ar->ar_flags = flags; 53} 54 55/* 56 * uvm_page_array_fini: clean up the array. 57 */ 58 59void 60uvm_page_array_fini(struct uvm_page_array *ar) 61{ 62 63 /* 64 * currently nothing to do. 65 */ 66#if defined(DIAGNOSTIC) 67 /* 68 * poison to trigger assertion in uvm_page_array_peek to 69 * detect usage errors. 70 */ 71 ar->ar_npages = 1; 72 ar->ar_idx = 1000; 73#endif /* defined(DIAGNOSTIC) */ 74} 75 76/* 77 * uvm_page_array_clear: forget the cached pages and initialize the array. 78 */ 79 80void 81uvm_page_array_clear(struct uvm_page_array *ar) 82{ 83 84 KASSERT(ar->ar_idx <= ar->ar_npages); 85 ar->ar_idx = 0; 86 ar->ar_npages = 0; 87} 88 89/* 90 * uvm_page_array_peek: return the next cached page. 91 */ 92 93struct vm_page * 94uvm_page_array_peek(struct uvm_page_array *ar) 95{ 96 97 KASSERT(ar->ar_idx <= ar->ar_npages); 98 if (ar->ar_idx == ar->ar_npages) { 99 return NULL; 100 } 101 return ar->ar_pages[ar->ar_idx]; 102} 103 104/* 105 * uvm_page_array_advance: advance the array to the next cached page 106 */ 107 108void 109uvm_page_array_advance(struct uvm_page_array *ar) 110{ 111 112 KASSERT(ar->ar_idx <= ar->ar_npages); 113 ar->ar_idx++; 114 KASSERT(ar->ar_idx <= ar->ar_npages); 115} 116 117/* 118 * uvm_page_array_fill: lookup pages and keep them cached. 119 * 120 * return 0 on success. in that case, cache the result in the array 121 * so that they will be picked by later uvm_page_array_peek. 122 * 123 * nwant is a number of pages to fetch. a caller should consider it a hint. 124 * nwant == 0 means a caller have no specific idea. 125 * 126 * return ENOENT if no pages are found. 127 * 128 * called with object lock held. 129 */ 130 131int 132uvm_page_array_fill(struct uvm_page_array *ar, voff_t off, unsigned int nwant) 133{ 134 unsigned int npages; 135#if defined(DEBUG) 136 unsigned int i; 137#endif /* defined(DEBUG) */ 138 unsigned int maxpages = __arraycount(ar->ar_pages); 139 struct uvm_object *uobj = ar->ar_uobj; 140 const int flags = ar->ar_flags; 141 const bool dense = (flags & UVM_PAGE_ARRAY_FILL_DENSE) != 0; 142 const bool backward = (flags & UVM_PAGE_ARRAY_FILL_BACKWARD) != 0; 143 int error = 0; 144 145 if (nwant != 0 && nwant < maxpages) { 146 maxpages = nwant; 147 } 148#if 0 /* called from DDB for "show obj/f" without lock */ 149 KASSERT(rw_lock_held(uobj->vmobjlock)); 150#endif 151 KASSERT(uvm_page_array_peek(ar) == NULL); 152 if ((flags & UVM_PAGE_ARRAY_FILL_DIRTY) != 0) { 153 unsigned int tagmask = UVM_PAGE_DIRTY_TAG; 154 155 if ((flags & UVM_PAGE_ARRAY_FILL_WRITEBACK) != 0) { 156 tagmask |= UVM_PAGE_WRITEBACK_TAG; 157 } 158 npages = 159 (backward ? radix_tree_gang_lookup_tagged_node_reverse : 160 radix_tree_gang_lookup_tagged_node)( 161 &uobj->uo_pages, off >> PAGE_SHIFT, (void **)ar->ar_pages, 162 maxpages, dense, tagmask); 163 } else { 164 npages = 165 (backward ? radix_tree_gang_lookup_node_reverse : 166 radix_tree_gang_lookup_node)( 167 &uobj->uo_pages, off >> PAGE_SHIFT, (void **)ar->ar_pages, 168 maxpages, dense); 169 } 170 if (npages == 0) { 171 if (flags != 0) { 172 /* 173 * if dense or looking for tagged entries (or 174 * working backwards), fail right away. 175 */ 176 npages = 0; 177 } else { 178 /* 179 * there's nothing else to be found with the current 180 * set of arguments, in the current version of the 181 * tree. 182 * 183 * minimize repeated tree lookups by "finding" a 184 * null pointer, in case the caller keeps looping (a 185 * common use case). 186 */ 187 npages = 1; 188 ar->ar_pages[0] = NULL; 189 } 190 error = ENOENT; 191 } 192 KASSERT(npages <= maxpages); 193 ar->ar_npages = npages; 194 ar->ar_idx = 0; 195#if defined(DEBUG) 196 for (i = 0; error == 0 && i < ar->ar_npages; i++) { 197 struct vm_page * const pg = ar->ar_pages[i]; 198 199 KASSERT(pg != NULL); 200 KDASSERT(pg->uobject == uobj); 201 if (backward) { 202 KDASSERT(pg->offset <= off); 203 KDASSERT(i == 0 || 204 pg->offset < ar->ar_pages[i - 1]->offset); 205 } else { 206 KDASSERT(pg->offset >= off); 207 KDASSERT(i == 0 || 208 pg->offset > ar->ar_pages[i - 1]->offset); 209 } 210 } 211#endif /* defined(DEBUG) */ 212 return error; 213} 214 215/* 216 * uvm_page_array_fill_and_peek: 217 * same as uvm_page_array_peek except that, if the array is empty, try to fill 218 * it first. 219 */ 220 221struct vm_page * 222uvm_page_array_fill_and_peek(struct uvm_page_array *ar, voff_t off, 223 unsigned int nwant) 224{ 225 int error; 226 227 if (ar->ar_idx != ar->ar_npages) { 228 return ar->ar_pages[ar->ar_idx]; 229 } 230 error = uvm_page_array_fill(ar, off, nwant); 231 if (error != 0) { 232 return NULL; 233 } 234 return uvm_page_array_peek(ar); 235} 236