1 /* 2 * Copyright (C) 2007 Jens Axboe <jens.axboe@oracle.com> 3 * 4 * Scatterlist handling helpers. 5 * 6 * This source code is licensed under the GNU General Public License, 7 * Version 2. See the file COPYING for more details. 8 */ 9 #include <linux/module.h> 10 #include <linux/scatterlist.h> 11 #include <linux/highmem.h> 12 13 /** 14 * sg_next - return the next scatterlist entry in a list 15 * @sg: The current sg entry 16 * 17 * Description: 18 * Usually the next entry will be @sg@ + 1, but if this sg element is part 19 * of a chained scatterlist, it could jump to the start of a new 20 * scatterlist array. 21 * 22 **/ 23 struct scatterlist *sg_next(struct scatterlist *sg) 24 { 25 #ifdef CONFIG_DEBUG_SG 26 BUG_ON(sg->sg_magic != SG_MAGIC); 27 #endif 28 if (sg_is_last(sg)) 29 return NULL; 30 31 sg++; 32 if (unlikely(sg_is_chain(sg))) 33 sg = sg_chain_ptr(sg); 34 35 return sg; 36 } 37 EXPORT_SYMBOL(sg_next); 38 39 /** 40 * sg_last - return the last scatterlist entry in a list 41 * @sgl: First entry in the scatterlist 42 * @nents: Number of entries in the scatterlist 43 * 44 * Description: 45 * Should only be used casually, it (currently) scans the entire list 46 * to get the last entry. 47 * 48 * Note that the @sgl@ pointer passed in need not be the first one, 49 * the important bit is that @nents@ denotes the number of entries that 50 * exist from @sgl@. 51 * 52 **/ 53 struct scatterlist *sg_last(struct scatterlist *sgl, unsigned int nents) 54 { 55 #ifndef ARCH_HAS_SG_CHAIN 56 struct scatterlist *ret = &sgl[nents - 1]; 57 #else 58 struct scatterlist *sg, *ret = NULL; 59 unsigned int i; 60 61 for_each_sg(sgl, sg, nents, i) 62 ret = sg; 63 64 #endif 65 #ifdef CONFIG_DEBUG_SG 66 BUG_ON(sgl[0].sg_magic != SG_MAGIC); 67 BUG_ON(!sg_is_last(ret)); 68 #endif 69 return ret; 70 } 71 EXPORT_SYMBOL(sg_last); 72 73 /** 74 * sg_init_table - Initialize SG table 75 * @sgl: The SG table 76 * @nents: Number of entries in table 77 * 78 * Notes: 79 * If this is part of a chained sg table, sg_mark_end() should be 80 * used only on the last table part. 81 * 82 **/ 83 void sg_init_table(struct scatterlist *sgl, unsigned int nents) 84 { 85 memset(sgl, 0, sizeof(*sgl) * nents); 86 #ifdef CONFIG_DEBUG_SG 87 { 88 unsigned int i; 89 for (i = 0; i < nents; i++) 90 sgl[i].sg_magic = SG_MAGIC; 91 } 92 #endif 93 sg_mark_end(&sgl[nents - 1]); 94 } 95 EXPORT_SYMBOL(sg_init_table); 96 97 /** 98 * sg_init_one - Initialize a single entry sg list 99 * @sg: SG entry 100 * @buf: Virtual address for IO 101 * @buflen: IO length 102 * 103 **/ 104 void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen) 105 { 106 sg_init_table(sg, 1); 107 sg_set_buf(sg, buf, buflen); 108 } 109 EXPORT_SYMBOL(sg_init_one); 110 111 /* 112 * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree 113 * helpers. 114 */ 115 static struct scatterlist *sg_kmalloc(unsigned int nents, gfp_t gfp_mask) 116 { 117 if (nents == SG_MAX_SINGLE_ALLOC) 118 return (struct scatterlist *) __get_free_page(gfp_mask); 119 else 120 return kmalloc(nents * sizeof(struct scatterlist), gfp_mask); 121 } 122 123 static void sg_kfree(struct scatterlist *sg, unsigned int nents) 124 { 125 if (nents == SG_MAX_SINGLE_ALLOC) 126 free_page((unsigned long) sg); 127 else 128 kfree(sg); 129 } 130 131 /** 132 * __sg_free_table - Free a previously mapped sg table 133 * @table: The sg table header to use 134 * @max_ents: The maximum number of entries per single scatterlist 135 * @free_fn: Free function 136 * 137 * Description: 138 * Free an sg table previously allocated and setup with 139 * __sg_alloc_table(). The @max_ents value must be identical to 140 * that previously used with __sg_alloc_table(). 141 * 142 **/ 143 void __sg_free_table(struct sg_table *table, unsigned int max_ents, 144 sg_free_fn *free_fn) 145 { 146 struct scatterlist *sgl, *next; 147 148 if (unlikely(!table->sgl)) 149 return; 150 151 sgl = table->sgl; 152 while (table->orig_nents) { 153 unsigned int alloc_size = table->orig_nents; 154 unsigned int sg_size; 155 156 /* 157 * If we have more than max_ents segments left, 158 * then assign 'next' to the sg table after the current one. 159 * sg_size is then one less than alloc size, since the last 160 * element is the chain pointer. 161 */ 162 if (alloc_size > max_ents) { 163 next = sg_chain_ptr(&sgl[max_ents - 1]); 164 alloc_size = max_ents; 165 sg_size = alloc_size - 1; 166 } else { 167 sg_size = alloc_size; 168 next = NULL; 169 } 170 171 table->orig_nents -= sg_size; 172 free_fn(sgl, alloc_size); 173 sgl = next; 174 } 175 176 table->sgl = NULL; 177 } 178 EXPORT_SYMBOL(__sg_free_table); 179 180 /** 181 * sg_free_table - Free a previously allocated sg table 182 * @table: The mapped sg table header 183 * 184 **/ 185 void sg_free_table(struct sg_table *table) 186 { 187 __sg_free_table(table, SG_MAX_SINGLE_ALLOC, sg_kfree); 188 } 189 EXPORT_SYMBOL(sg_free_table); 190 191 /** 192 * __sg_alloc_table - Allocate and initialize an sg table with given allocator 193 * @table: The sg table header to use 194 * @nents: Number of entries in sg list 195 * @max_ents: The maximum number of entries the allocator returns per call 196 * @gfp_mask: GFP allocation mask 197 * @alloc_fn: Allocator to use 198 * 199 * Description: 200 * This function returns a @table @nents long. The allocator is 201 * defined to return scatterlist chunks of maximum size @max_ents. 202 * Thus if @nents is bigger than @max_ents, the scatterlists will be 203 * chained in units of @max_ents. 204 * 205 * Notes: 206 * If this function returns non-0 (eg failure), the caller must call 207 * __sg_free_table() to cleanup any leftover allocations. 208 * 209 **/ 210 int __sg_alloc_table(struct sg_table *table, unsigned int nents, 211 unsigned int max_ents, gfp_t gfp_mask, 212 sg_alloc_fn *alloc_fn) 213 { 214 struct scatterlist *sg, *prv; 215 unsigned int left; 216 217 #ifndef ARCH_HAS_SG_CHAIN 218 BUG_ON(nents > max_ents); 219 #endif 220 221 memset(table, 0, sizeof(*table)); 222 223 left = nents; 224 prv = NULL; 225 do { 226 unsigned int sg_size, alloc_size = left; 227 228 if (alloc_size > max_ents) { 229 alloc_size = max_ents; 230 sg_size = alloc_size - 1; 231 } else 232 sg_size = alloc_size; 233 234 left -= sg_size; 235 236 sg = alloc_fn(alloc_size, gfp_mask); 237 if (unlikely(!sg)) 238 return -ENOMEM; 239 240 sg_init_table(sg, alloc_size); 241 table->nents = table->orig_nents += sg_size; 242 243 /* 244 * If this is the first mapping, assign the sg table header. 245 * If this is not the first mapping, chain previous part. 246 */ 247 if (prv) 248 sg_chain(prv, max_ents, sg); 249 else 250 table->sgl = sg; 251 252 /* 253 * If no more entries after this one, mark the end 254 */ 255 if (!left) 256 sg_mark_end(&sg[sg_size - 1]); 257 258 /* 259 * only really needed for mempool backed sg allocations (like 260 * SCSI), a possible improvement here would be to pass the 261 * table pointer into the allocator and let that clear these 262 * flags 263 */ 264 gfp_mask &= ~__GFP_WAIT; 265 gfp_mask |= __GFP_HIGH; 266 prv = sg; 267 } while (left); 268 269 return 0; 270 } 271 EXPORT_SYMBOL(__sg_alloc_table); 272 273 /** 274 * sg_alloc_table - Allocate and initialize an sg table 275 * @table: The sg table header to use 276 * @nents: Number of entries in sg list 277 * @gfp_mask: GFP allocation mask 278 * 279 * Description: 280 * Allocate and initialize an sg table. If @nents@ is larger than 281 * SG_MAX_SINGLE_ALLOC a chained sg table will be setup. 282 * 283 **/ 284 int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask) 285 { 286 int ret; 287 288 ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC, 289 gfp_mask, sg_kmalloc); 290 if (unlikely(ret)) 291 __sg_free_table(table, SG_MAX_SINGLE_ALLOC, sg_kfree); 292 293 return ret; 294 } 295 EXPORT_SYMBOL(sg_alloc_table); 296 297 /** 298 * sg_copy_buffer - Copy data between a linear buffer and an SG list 299 * @sgl: The SG list 300 * @nents: Number of SG entries 301 * @buf: Where to copy from 302 * @buflen: The number of bytes to copy 303 * @to_buffer: transfer direction (non zero == from an sg list to a 304 * buffer, 0 == from a buffer to an sg list 305 * 306 * Returns the number of copied bytes. 307 * 308 **/ 309 static size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, 310 void *buf, size_t buflen, int to_buffer) 311 { 312 struct scatterlist *sg; 313 size_t buf_off = 0; 314 int i; 315 316 WARN_ON(!irqs_disabled()); 317 318 for_each_sg(sgl, sg, nents, i) { 319 struct page *page; 320 int n = 0; 321 unsigned int sg_off = sg->offset; 322 unsigned int sg_copy = sg->length; 323 324 if (sg_copy > buflen) 325 sg_copy = buflen; 326 buflen -= sg_copy; 327 328 while (sg_copy > 0) { 329 unsigned int page_copy; 330 void *p; 331 332 page_copy = PAGE_SIZE - sg_off; 333 if (page_copy > sg_copy) 334 page_copy = sg_copy; 335 336 page = nth_page(sg_page(sg), n); 337 p = kmap_atomic(page, KM_BIO_SRC_IRQ); 338 339 if (to_buffer) 340 memcpy(buf + buf_off, p + sg_off, page_copy); 341 else { 342 memcpy(p + sg_off, buf + buf_off, page_copy); 343 flush_kernel_dcache_page(page); 344 } 345 346 kunmap_atomic(p, KM_BIO_SRC_IRQ); 347 348 buf_off += page_copy; 349 sg_off += page_copy; 350 if (sg_off == PAGE_SIZE) { 351 sg_off = 0; 352 n++; 353 } 354 sg_copy -= page_copy; 355 } 356 357 if (!buflen) 358 break; 359 } 360 361 return buf_off; 362 } 363 364 /** 365 * sg_copy_from_buffer - Copy from a linear buffer to an SG list 366 * @sgl: The SG list 367 * @nents: Number of SG entries 368 * @buf: Where to copy from 369 * @buflen: The number of bytes to copy 370 * 371 * Returns the number of copied bytes. 372 * 373 **/ 374 size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents, 375 void *buf, size_t buflen) 376 { 377 return sg_copy_buffer(sgl, nents, buf, buflen, 0); 378 } 379 EXPORT_SYMBOL(sg_copy_from_buffer); 380 381 /** 382 * sg_copy_to_buffer - Copy from an SG list to a linear buffer 383 * @sgl: The SG list 384 * @nents: Number of SG entries 385 * @buf: Where to copy to 386 * @buflen: The number of bytes to copy 387 * 388 * Returns the number of copied bytes. 389 * 390 **/ 391 size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents, 392 void *buf, size_t buflen) 393 { 394 return sg_copy_buffer(sgl, nents, buf, buflen, 1); 395 } 396 EXPORT_SYMBOL(sg_copy_to_buffer); 397