linux/lib/scatterlist.c
<<
>>
Prefs
   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
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.