scatterlist.c revision 50bed2e2862a8f3a4f7d683d0d27292e71ef18b9
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 **/ 23struct 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} 37EXPORT_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 **/ 53struct 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} 71EXPORT_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 **/ 83void 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} 95EXPORT_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 **/ 104void 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} 109EXPORT_SYMBOL(sg_init_one); 110 111/* 112 * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree 113 * helpers. 114 */ 115static 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 123static 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 **/ 143void __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} 178EXPORT_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 **/ 185void sg_free_table(struct sg_table *table) 186{ 187 __sg_free_table(table, SG_MAX_SINGLE_ALLOC, sg_kfree); 188} 189EXPORT_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 **/ 210int __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} 271EXPORT_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 **/ 284int 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} 295EXPORT_SYMBOL(sg_alloc_table); 296 297/** 298 * sg_miter_start - start mapping iteration over a sg list 299 * @miter: sg mapping iter to be started 300 * @sgl: sg list to iterate over 301 * @nents: number of sg entries 302 * 303 * Description: 304 * Starts mapping iterator @miter. 305 * 306 * Context: 307 * Don't care. 308 */ 309void sg_miter_start(struct sg_mapping_iter *miter, struct scatterlist *sgl, 310 unsigned int nents, unsigned int flags) 311{ 312 memset(miter, 0, sizeof(struct sg_mapping_iter)); 313 314 miter->__sg = sgl; 315 miter->__nents = nents; 316 miter->__offset = 0; 317 miter->__flags = flags; 318} 319EXPORT_SYMBOL(sg_miter_start); 320 321/** 322 * sg_miter_next - proceed mapping iterator to the next mapping 323 * @miter: sg mapping iter to proceed 324 * 325 * Description: 326 * Proceeds @miter@ to the next mapping. @miter@ should have been 327 * started using sg_miter_start(). On successful return, 328 * @miter@->page, @miter@->addr and @miter@->length point to the 329 * current mapping. 330 * 331 * Context: 332 * IRQ disabled if SG_MITER_ATOMIC. IRQ must stay disabled till 333 * @miter@ is stopped. May sleep if !SG_MITER_ATOMIC. 334 * 335 * Returns: 336 * true if @miter contains the next mapping. false if end of sg 337 * list is reached. 338 */ 339bool sg_miter_next(struct sg_mapping_iter *miter) 340{ 341 unsigned int off, len; 342 343 /* check for end and drop resources from the last iteration */ 344 if (!miter->__nents) 345 return false; 346 347 sg_miter_stop(miter); 348 349 /* get to the next sg if necessary. __offset is adjusted by stop */ 350 if (miter->__offset == miter->__sg->length && --miter->__nents) { 351 miter->__sg = sg_next(miter->__sg); 352 miter->__offset = 0; 353 } 354 355 /* map the next page */ 356 off = miter->__sg->offset + miter->__offset; 357 len = miter->__sg->length - miter->__offset; 358 359 miter->page = nth_page(sg_page(miter->__sg), off >> PAGE_SHIFT); 360 off &= ~PAGE_MASK; 361 miter->length = min_t(unsigned int, len, PAGE_SIZE - off); 362 miter->consumed = miter->length; 363 364 if (miter->__flags & SG_MITER_ATOMIC) 365 miter->addr = kmap_atomic(miter->page, KM_BIO_SRC_IRQ) + off; 366 else 367 miter->addr = kmap(miter->page) + off; 368 369 return true; 370} 371EXPORT_SYMBOL(sg_miter_next); 372 373/** 374 * sg_miter_stop - stop mapping iteration 375 * @miter: sg mapping iter to be stopped 376 * 377 * Description: 378 * Stops mapping iterator @miter. @miter should have been started 379 * started using sg_miter_start(). A stopped iteration can be 380 * resumed by calling sg_miter_next() on it. This is useful when 381 * resources (kmap) need to be released during iteration. 382 * 383 * Context: 384 * IRQ disabled if the SG_MITER_ATOMIC is set. Don't care otherwise. 385 */ 386void sg_miter_stop(struct sg_mapping_iter *miter) 387{ 388 WARN_ON(miter->consumed > miter->length); 389 390 /* drop resources from the last iteration */ 391 if (miter->addr) { 392 miter->__offset += miter->consumed; 393 394 if (miter->__flags & SG_MITER_ATOMIC) { 395 WARN_ON(!irqs_disabled()); 396 kunmap_atomic(miter->addr, KM_BIO_SRC_IRQ); 397 } else 398 kunmap(miter->addr); 399 400 miter->page = NULL; 401 miter->addr = NULL; 402 miter->length = 0; 403 miter->consumed = 0; 404 } 405} 406EXPORT_SYMBOL(sg_miter_stop); 407 408/** 409 * sg_copy_buffer - Copy data between a linear buffer and an SG list 410 * @sgl: The SG list 411 * @nents: Number of SG entries 412 * @buf: Where to copy from 413 * @buflen: The number of bytes to copy 414 * @to_buffer: transfer direction (non zero == from an sg list to a 415 * buffer, 0 == from a buffer to an sg list 416 * 417 * Returns the number of copied bytes. 418 * 419 **/ 420static size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, 421 void *buf, size_t buflen, int to_buffer) 422{ 423 unsigned int offset = 0; 424 struct sg_mapping_iter miter; 425 unsigned long flags; 426 427 sg_miter_start(&miter, sgl, nents, SG_MITER_ATOMIC); 428 429 local_irq_save(flags); 430 431 while (sg_miter_next(&miter) && offset < buflen) { 432 unsigned int len; 433 434 len = min(miter.length, buflen - offset); 435 436 if (to_buffer) 437 memcpy(buf + offset, miter.addr, len); 438 else { 439 memcpy(miter.addr, buf + offset, len); 440 flush_kernel_dcache_page(miter.page); 441 } 442 443 offset += len; 444 } 445 446 sg_miter_stop(&miter); 447 448 local_irq_restore(flags); 449 return offset; 450} 451 452/** 453 * sg_copy_from_buffer - Copy from a linear buffer to an SG list 454 * @sgl: The SG list 455 * @nents: Number of SG entries 456 * @buf: Where to copy from 457 * @buflen: The number of bytes to copy 458 * 459 * Returns the number of copied bytes. 460 * 461 **/ 462size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents, 463 void *buf, size_t buflen) 464{ 465 return sg_copy_buffer(sgl, nents, buf, buflen, 0); 466} 467EXPORT_SYMBOL(sg_copy_from_buffer); 468 469/** 470 * sg_copy_to_buffer - Copy from an SG list to a linear buffer 471 * @sgl: The SG list 472 * @nents: Number of SG entries 473 * @buf: Where to copy to 474 * @buflen: The number of bytes to copy 475 * 476 * Returns the number of copied bytes. 477 * 478 **/ 479size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents, 480 void *buf, size_t buflen) 481{ 482 return sg_copy_buffer(sgl, nents, buf, buflen, 1); 483} 484EXPORT_SYMBOL(sg_copy_to_buffer); 485