File: /usr/src/linux/arch/ia64/sn/io/alenlist.c
1 /* $Id$
2 *
3 * This file is subject to the terms and conditions of the GNU General Public
4 * License. See the file "COPYING" in the main directory of this archive
5 * for more details.
6 *
7 * Copyright (C) 1992 - 1997, 2000 Silicon Graphics, Inc.
8 * Copyright (C) 2000 by Colin Ngam
9 */
10
11 /* Implementation of Address/Length Lists. */
12
13
14 #include <linux/types.h>
15 #include <linux/slab.h>
16 #include <asm/sn/sgi.h>
17 #include <asm/sn/alenlist.h>
18 #include <asm/sn/mmzone_sn1.h>
19
20 /*
21 * Logically, an Address/Length List is a list of Pairs, where each pair
22 * holds an Address and a Length, all in some Address Space. In this
23 * context, "Address Space" is a particular Crosstalk Widget address
24 * space, a PCI device address space, a VME bus address space, a
25 * physical memory address space, etc.
26 *
27 * The main use for these Lists is to provide a single mechanism that
28 * describes where in an address space a DMA occurs. This allows the
29 * various I/O Bus support layers to provide a single interface for
30 * DMA mapping and DMA translation without regard to how the DMA target
31 * was specified by upper layers. The upper layers commonly specify a
32 * DMA target via a buf structure page list, a kernel virtual address,
33 * a user virtual address, a vector of addresses (a la uio and iov),
34 * or possibly a pfn list.
35 *
36 * Address/Length Lists also enable drivers to take advantage of their
37 * inate scatter/gather capabilities in systems where some address
38 * translation may be required between bus adapters. The driver forms
39 * a List that represents physical memory targets. This list is passed
40 * to the various adapters, which apply various translations. The final
41 * list that's returned to the driver is in terms of its local address
42 * address space -- addresses which can be passed off to a scatter/gather
43 * capable DMA controller.
44 *
45 * The current implementation is intended to be useful both in kernels
46 * that support interrupt threads (INTR_KTHREAD) and in systems that do
47 * not support interrupt threads. Of course, in the latter case, some
48 * interfaces can be called only within a suspendable context.
49 *
50 * Basic operations on Address/Length Lists include:
51 * alenlist_create Create a list
52 * alenlist_clear Clear a list
53 * alenlist_destroy Destroy a list
54 * alenlist_append Append a Pair to the end of a list
55 * alenlist_replace Replace a Pair in the middle of a list
56 * alenlist_get Get an Address/Length Pair from a list
57 * alenlist_size Return the number of Pairs in a list
58 * alenlist_concat Append one list to the end of another
59 * alenlist_clone Create a new copy of a list
60 *
61 * Operations that convert from upper-level specifications to Address/
62 * Length Lists currently include:
63 * kvaddr_to_alenlist Convert from a kernel virtual address
64 * uvaddr_to_alenlist Convert from a user virtual address
65 * buf_to_alenlist Convert from a buf structure
66 * alenlist_done Tell system that we're done with an alenlist
67 * obtained from a conversion.
68 * Additional convenience operations:
69 * alenpair_init Create a list and initialize it with a Pair
70 * alenpair_get Peek at the first pair on a List
71 *
72 * A supporting type for Address/Length Lists is an alenlist_cursor_t. A
73 * cursor marks a position in a List, and determines which Pair is fetched
74 * by alenlist_get.
75 * alenlist_cursor_create Allocate and initialize a cursor
76 * alenlist_cursor_destroy Free space consumed by a cursor
77 * alenlist_cursor_init (Re-)Initialize a cursor to point
78 * to the start of a list
79 * alenlist_cursor_clone Clone a cursor (at the current offset)
80 * alenlist_cursor_offset Return the number of bytes into
81 * a list that this cursor marks
82 * Multiple cursors can point at various points into a List. Also, each
83 * list maintains one "internal cursor" which may be updated by alenlist_clear
84 * and alenlist_get. If calling code simply wishes to scan sequentially
85 * through a list starting at the beginning, and if it is the only user of
86 * a list, it can rely on this internal cursor rather than managing a
87 * separate explicit cursor.
88 *
89 * The current implementation allows callers to allocate both cursors and
90 * the lists as local stack (structure) variables. This allows for some
91 * extra efficiency at the expense of forward binary compatibility. It
92 * is recommended that customer drivers refrain from local allocation.
93 * In fact, we likely will choose to move the structures out of the public
94 * header file into a private place in order to discourage this usage.
95 *
96 * Currently, no locking is provided by the alenlist implementation.
97 *
98 * Implementation notes:
99 * For efficiency, Pairs are grouped into "chunks" of, say, 32 Pairs
100 * and a List consists of some number of these chunks. Chunks are completely
101 * invisible to calling code. Chunks should be large enough to hold most
102 * standard-sized DMA's, but not so large that they consume excessive space.
103 *
104 * It is generally expected that Lists will be constructed at one time and
105 * scanned at a later time. It is NOT expected that drivers will scan
106 * a List while the List is simultaneously extended, although this is
107 * theoretically possible with sufficient upper-level locking.
108 *
109 * In order to support demands of Real-Time drivers and in order to support
110 * swapping under low-memory conditions, we support the concept of a
111 * "pre-allocated fixed-sized List". After creating a List with
112 * alenlist_create, a driver may explicitly grow the list (via "alenlist_grow")
113 * to a specific number of Address/Length pairs. It is guaranteed that future
114 * operations involving this list will never automatically grow the list
115 * (i.e. if growth is ever required, the operation will fail). Additionally,
116 * operations that use alenlist's (e.g. DMA operations) accept a flag which
117 * causes processing to take place "in-situ"; that is, the input alenlist
118 * entries are replaced with output alenlist entries. The combination of
119 * pre-allocated Lists and in-situ processing allows us to avoid the
120 * potential deadlock scenario where we sleep (waiting for memory) in the
121 * swap out path.
122 *
123 * For debugging, we track the number of allocated Lists in alenlist_count
124 * the number of allocated chunks in alenlist_chunk_count, and the number
125 * of allocate cursors in alenlist_cursor_count. We also provide a debug
126 * routine, alenlist_show, which dumps the contents of an Address/Length List.
127 *
128 * Currently, Lists are formed by drivers on-demand. Eventually, we may
129 * associate an alenlist with a buf structure and keep it up to date as
130 * we go along. In that case, buf_to_alenlist simply returns a pointer
131 * to the existing List, and increments the Lists's reference count.
132 * alenlist_done would decrement the reference count and destroys the List
133 * if it was the last reference.
134 *
135 * Eventually alenlist's may allow better support for user-level scatter/
136 * gather operations (e.g. via readv/writev): With proper support, we
137 * could potentially handle a vector of reads with a single scatter/gather
138 * DMA operation. This could be especially useful on NUMA systems where
139 * there's more of a reason for users to use vector I/O operations.
140 *
141 * Eventually, alenlist's may replace kaio lists, vhand page lists,
142 * buffer cache pfdat lists, DMA page lists, etc.
143 */
144
145 /* Opaque data types */
146
147 /* An Address/Length pair. */
148 typedef struct alen_s {
149 alenaddr_t al_addr;
150 size_t al_length;
151 } alen_t;
152
153 /*
154 * Number of elements in one chunk of an Address/Length List.
155 *
156 * This size should be sufficient to hold at least an "average" size
157 * DMA request. Must be at least 1, and should be a power of 2,
158 * for efficiency.
159 */
160 #define ALEN_CHUNK_SZ ((512*1024)/NBPP)
161
162 /*
163 * A fixed-size set of Address/Length Pairs. Chunks of Pairs are strung together
164 * to form a complete Address/Length List. Chunking is entirely hidden within the
165 * alenlist implementation, and it simply makes allocation and growth of lists more
166 * efficient.
167 */
168 typedef struct alenlist_chunk_s {
169 alen_t alc_pair[ALEN_CHUNK_SZ];/* list of addr/len pairs */
170 struct alenlist_chunk_s *alc_next; /* point to next chunk of pairs */
171 } *alenlist_chunk_t;
172
173 /*
174 * An Address/Length List. An Address/Length List is allocated with alenlist_create.
175 * Alternatively, a list can be allocated on the stack (local variable of type
176 * alenlist_t) and initialized with alenpair_init or with a combination of
177 * alenlist_clear and alenlist_append, etc. Code which statically allocates these
178 * structures loses forward binary compatibility!
179 *
180 * A statically allocated List is sufficiently large to hold ALEN_CHUNK_SZ pairs.
181 */
182 struct alenlist_s {
183 unsigned short al_flags;
184 unsigned short al_logical_size; /* logical size of list, in pairs */
185 unsigned short al_actual_size; /* actual size of list, in pairs */
186 struct alenlist_chunk_s *al_last_chunk; /* pointer to last logical chunk */
187 struct alenlist_cursor_s al_cursor; /* internal cursor */
188 struct alenlist_chunk_s al_chunk; /* initial set of pairs */
189 alenaddr_t al_compaction_address; /* used to compact pairs */
190 };
191
192 /* al_flags field */
193 #define AL_FIXED_SIZE 0x1 /* List is pre-allocated, and of fixed size */
194
195
196 zone_t *alenlist_zone = NULL;
197 zone_t *alenlist_chunk_zone = NULL;
198 zone_t *alenlist_cursor_zone = NULL;
199
200 #if DEBUG
201 int alenlist_count=0; /* Currently allocated Lists */
202 int alenlist_chunk_count = 0; /* Currently allocated chunks */
203 int alenlist_cursor_count = 0; /* Currently allocate cursors */
204 #define INCR_COUNT(ptr) atomic_inc((ptr));
205 #define DECR_COUNT(ptr) atomic_dec((ptr));
206 #else
207 #define INCR_COUNT(ptr)
208 #define DECR_COUNT(ptr)
209 #endif /* DEBUG */
210
211 #if DEBUG
212 static void alenlist_show(alenlist_t);
213 #endif /* DEBUG */
214
215 /*
216 * Initialize Address/Length List management. One time initialization.
217 */
218 void
219 alenlist_init(void)
220 {
221 alenlist_zone = kmem_zone_init(sizeof(struct alenlist_s), "alenlist");
222 alenlist_chunk_zone = kmem_zone_init(sizeof(struct alenlist_chunk_s), "alchunk");
223 alenlist_cursor_zone = kmem_zone_init(sizeof(struct alenlist_cursor_s), "alcursor");
224 #if DEBUG
225 idbg_addfunc("alenshow", alenlist_show);
226 #endif /* DEBUG */
227 }
228
229
230 /*
231 * Initialize an Address/Length List cursor.
232 */
233 static void
234 do_cursor_init(alenlist_t alenlist, alenlist_cursor_t cursorp)
235 {
236 cursorp->al_alenlist = alenlist;
237 cursorp->al_offset = 0;
238 cursorp->al_chunk = &alenlist->al_chunk;
239 cursorp->al_index = 0;
240 cursorp->al_bcount = 0;
241 }
242
243
244 /*
245 * Create an Address/Length List, and clear it.
246 * Set the cursor to the beginning.
247 */
248 alenlist_t
249 alenlist_create(unsigned flags)
250 {
251 alenlist_t alenlist;
252
253 alenlist = kmem_zone_alloc(alenlist_zone, flags & AL_NOSLEEP ? VM_NOSLEEP : 0);
254 if (alenlist) {
255 INCR_COUNT(&alenlist_count);
256
257 alenlist->al_flags = 0;
258 alenlist->al_logical_size = 0;
259 alenlist->al_actual_size = ALEN_CHUNK_SZ;
260 alenlist->al_last_chunk = &alenlist->al_chunk;
261 alenlist->al_chunk.alc_next = NULL;
262 do_cursor_init(alenlist, &alenlist->al_cursor);
263 }
264
265 return(alenlist);
266 }
267
268
269 /*
270 * Grow an Address/Length List so that all resources needed to contain
271 * the specified number of Pairs are pre-allocated. An Address/Length
272 * List that has been explicitly "grown" will never *automatically*
273 * grow, shrink, or be destroyed.
274 *
275 * Pre-allocation is useful for Real-Time drivers and for drivers that
276 * may be used along the swap-out path and therefore cannot afford to
277 * sleep until memory is freed.
278 *
279 * The cursor is set to the beginning of the list.
280 */
281 int
282 alenlist_grow(alenlist_t alenlist, size_t npairs)
283 {
284 /*
285 * This interface should be used relatively rarely, so
286 * the implementation is kept simple: We clear the List,
287 * then append npairs bogus entries. Finally, we mark
288 * the list as FIXED_SIZE and re-initialize the internal
289 * cursor.
290 */
291
292 /*
293 * Temporarily mark as non-fixed size, since we're about
294 * to shrink and expand it.
295 */
296 alenlist->al_flags &= ~AL_FIXED_SIZE;
297
298 /* Free whatever was in the alenlist. */
299 alenlist_clear(alenlist);
300
301 /* Allocate everything that we need via automatic expansion. */
302 while (npairs--)
303 if (alenlist_append(alenlist, 0, 0, AL_NOCOMPACT) == ALENLIST_FAILURE)
304 return(ALENLIST_FAILURE);
305
306 /* Now, mark as FIXED_SIZE */
307 alenlist->al_flags |= AL_FIXED_SIZE;
308
309 /* Clear out bogus entries */
310 alenlist_clear(alenlist);
311
312 /* Initialize internal cursor to the beginning */
313 do_cursor_init(alenlist, &alenlist->al_cursor);
314
315 return(ALENLIST_SUCCESS);
316 }
317
318
319 /*
320 * Clear an Address/Length List so that it holds no pairs.
321 */
322 void
323 alenlist_clear(alenlist_t alenlist)
324 {
325 alenlist_chunk_t chunk, freechunk;
326
327 /*
328 * If this List is not FIXED_SIZE, free all the
329 * extra chunks.
330 */
331 if (!(alenlist->al_flags & AL_FIXED_SIZE)) {
332 /* First, free any extension alenlist chunks */
333 chunk = alenlist->al_chunk.alc_next;
334 while (chunk) {
335 freechunk = chunk;
336 chunk = chunk->alc_next;
337 kmem_zone_free(alenlist_chunk_zone, freechunk);
338 DECR_COUNT(&alenlist_chunk_count);
339 }
340 alenlist->al_actual_size = ALEN_CHUNK_SZ;
341 alenlist->al_chunk.alc_next = NULL;
342 }
343
344 alenlist->al_logical_size = 0;
345 alenlist->al_last_chunk = &alenlist->al_chunk;
346 do_cursor_init(alenlist, &alenlist->al_cursor);
347 }
348
349
350 /*
351 * Create and initialize an Address/Length Pair.
352 * This is intended for degenerate lists, consisting of a single
353 * address/length pair.
354 */
355 alenlist_t
356 alenpair_init( alenaddr_t address,
357 size_t length)
358 {
359 alenlist_t alenlist;
360
361 alenlist = alenlist_create(0);
362
363 alenlist->al_logical_size = 1;
364 ASSERT(alenlist->al_last_chunk == &alenlist->al_chunk);
365 alenlist->al_chunk.alc_pair[0].al_length = length;
366 alenlist->al_chunk.alc_pair[0].al_addr = address;
367
368 return(alenlist);
369 }
370
371 /*
372 * Return address/length from a degenerate (1-pair) List, or
373 * first pair from a larger list. Does NOT update the internal cursor,
374 * so this is an easy way to peek at a start address.
375 */
376 int
377 alenpair_get( alenlist_t alenlist,
378 alenaddr_t *address,
379 size_t *length)
380 {
381 if (alenlist->al_logical_size == 0)
382 return(ALENLIST_FAILURE);
383
384 *length = alenlist->al_chunk.alc_pair[0].al_length;
385 *address = alenlist->al_chunk.alc_pair[0].al_addr;
386 return(ALENLIST_SUCCESS);
387 }
388
389
390 /*
391 * Destroy an Address/Length List.
392 */
393 void
394 alenlist_destroy(alenlist_t alenlist)
395 {
396 if (alenlist == NULL)
397 return;
398
399 /*
400 * Turn off FIXED_SIZE so this List can be
401 * automatically shrunk.
402 */
403 alenlist->al_flags &= ~AL_FIXED_SIZE;
404
405 /* Free extension chunks first */
406 if (alenlist->al_chunk.alc_next)
407 alenlist_clear(alenlist);
408
409 /* Now, free the alenlist itself */
410 kmem_zone_free(alenlist_zone, alenlist);
411 DECR_COUNT(&alenlist_count);
412 }
413
414 /*
415 * Release an Address/Length List.
416 * This is in preparation for a day when alenlist's may be longer-lived, and
417 * perhaps associated with a buf structure. We'd add a reference count, and
418 * this routine would decrement the count. For now, we create alenlist's on
419 * on demand and free them when done. If the driver is not explicitly managing
420 * a List for its own use, it should call alenlist_done rather than alenlist_destroy.
421 */
422 void
423 alenlist_done(alenlist_t alenlist)
424 {
425 alenlist_destroy(alenlist);
426 }
427
428
429 /*
430 * Append another address/length to the end of an Address/Length List,
431 * growing the list if permitted and necessary.
432 *
433 * Returns: SUCCESS/FAILURE
434 */
435 int
436 alenlist_append( alenlist_t alenlist, /* append to this list */
437 alenaddr_t address, /* address to append */
438 size_t length, /* length to append */
439 unsigned flags)
440 {
441 alen_t *alenp;
442 int index, last_index;
443
444 index = alenlist->al_logical_size % ALEN_CHUNK_SZ;
445
446 if ((alenlist->al_logical_size > 0)) {
447 /*
448 * See if we can compact this new pair in with the previous entry.
449 * al_compaction_address holds that value that we'd need to see
450 * in order to compact.
451 */
452 if (!(flags & AL_NOCOMPACT) &&
453 (alenlist->al_compaction_address == address)) {
454 last_index = (alenlist->al_logical_size-1) % ALEN_CHUNK_SZ;
455 alenp = &(alenlist->al_last_chunk->alc_pair[last_index]);
456 alenp->al_length += length;
457 alenlist->al_compaction_address += length;
458 return(ALENLIST_SUCCESS);
459 }
460
461 /*
462 * If we're out of room in this chunk, move to a new chunk.
463 */
464 if (index == 0) {
465 if (alenlist->al_flags & AL_FIXED_SIZE) {
466 alenlist->al_last_chunk = alenlist->al_last_chunk->alc_next;
467
468 /* If we're out of space in a FIXED_SIZE List, quit. */
469 if (alenlist->al_last_chunk == NULL) {
470 ASSERT(alenlist->al_logical_size == alenlist->al_actual_size);
471 return(ALENLIST_FAILURE);
472 }
473 } else {
474 alenlist_chunk_t new_chunk;
475
476 new_chunk = kmem_zone_alloc(alenlist_chunk_zone,
477 flags & AL_NOSLEEP ? VM_NOSLEEP : 0);
478
479 if (new_chunk == NULL)
480 return(ALENLIST_FAILURE);
481
482 alenlist->al_last_chunk->alc_next = new_chunk;
483 new_chunk->alc_next = NULL;
484 alenlist->al_last_chunk = new_chunk;
485 alenlist->al_actual_size += ALEN_CHUNK_SZ;
486 INCR_COUNT(&alenlist_chunk_count);
487 }
488 }
489 }
490
491 alenp = &(alenlist->al_last_chunk->alc_pair[index]);
492 alenp->al_addr = address;
493 alenp->al_length = length;
494
495 alenlist->al_logical_size++;
496 alenlist->al_compaction_address = address + length;
497
498 return(ALENLIST_SUCCESS);
499 }
500
501
502 /*
503 * Replace an item in an Address/Length List. Cursor is updated so
504 * that alenlist_get will get the next item in the list. This interface
505 * is not very useful for drivers; but it is useful to bus providers
506 * that need to translate between address spaced in situ. The old Address
507 * and Length are returned.
508 */
509 /* ARGSUSED */
510 int
511 alenlist_replace( alenlist_t alenlist, /* in: replace in this list */
512 alenlist_cursor_t cursorp, /* inout: which item to replace */
513 alenaddr_t *addrp, /* inout: address */
514 size_t *lengthp, /* inout: length */
515 unsigned flags)
516 {
517 alen_t *alenp;
518 alenlist_chunk_t chunk;
519 unsigned int index;
520 size_t length;
521 alenaddr_t addr;
522
523 if ((addrp == NULL) || (lengthp == NULL))
524 return(ALENLIST_FAILURE);
525
526 if (alenlist->al_logical_size == 0)
527 return(ALENLIST_FAILURE);
528
529 addr = *addrp;
530 length = *lengthp;
531
532 /*
533 * If no cursor explicitly specified, use the Address/Length List's
534 * internal cursor.
535 */
536 if (cursorp == NULL)
537 cursorp = &alenlist->al_cursor;
538
539 chunk = cursorp->al_chunk;
540 index = cursorp->al_index;
541
542 ASSERT(cursorp->al_alenlist == alenlist);
543 if (cursorp->al_alenlist != alenlist)
544 return(ALENLIST_FAILURE);
545
546 alenp = &chunk->alc_pair[index];
547
548 /* Return old values */
549 *addrp = alenp->al_length;
550 *lengthp = alenp->al_addr;
551
552 /* Set up new values */
553 alenp->al_length = length;
554 alenp->al_addr = addr;
555
556 /* Update cursor to point to next item */
557 cursorp->al_bcount = length;
558
559 return(ALENLIST_SUCCESS);
560 }
561
562
563 /*
564 * Initialize a cursor in order to walk an alenlist.
565 * An alenlist_cursor always points to the last thing that was obtained
566 * from the list. If al_chunk is NULL, then nothing has yet been obtained.
567 *
568 * Note: There is an "internal cursor" associated with every Address/Length List.
569 * For users that scan sequentially through a List, it is more efficient to
570 * simply use the internal cursor. The caller must insure that no other users
571 * will simultaneously scan the List. The caller can reposition the internal
572 * cursor by calling alenlist_cursor_init with a NULL cursorp.
573 */
574 int
575 alenlist_cursor_init(alenlist_t alenlist, size_t offset, alenlist_cursor_t cursorp)
576 {
577 size_t byte_count;
578
579 if (cursorp == NULL)
580 cursorp = &alenlist->al_cursor;
581
582 /* Get internal cursor's byte count for use as a hint.
583 *
584 * If the internal cursor points passed the point that we're interested in,
585 * we need to seek forward from the beginning. Otherwise, we can seek forward
586 * from the internal cursor.
587 */
588 if ((offset > 0) &&
589 ((byte_count = alenlist_cursor_offset(alenlist, (alenlist_cursor_t)NULL)) <= offset)) {
590 offset -= byte_count;
591 alenlist_cursor_clone(alenlist, NULL, cursorp);
592 } else
593 do_cursor_init(alenlist, cursorp);
594
595 /* We could easily speed this up, but it shouldn't be used very often. */
596 while (offset != 0) {
597 alenaddr_t addr;
598 size_t length;
599
600 if (alenlist_get(alenlist, cursorp, offset, &addr, &length, 0) != ALENLIST_SUCCESS)
601 return(ALENLIST_FAILURE);
602 offset -= length;
603 }
604 return(ALENLIST_SUCCESS);
605 }
606
607
608 /*
609 * Copy a cursor. The source cursor is either an internal alenlist cursor
610 * or an explicit cursor.
611 */
612 int
613 alenlist_cursor_clone( alenlist_t alenlist,
614 alenlist_cursor_t cursorp_in,
615 alenlist_cursor_t cursorp_out)
616 {
617 ASSERT(cursorp_out);
618
619 if (alenlist && cursorp_in)
620 if (alenlist != cursorp_in->al_alenlist)
621 return(ALENLIST_FAILURE);
622
623 if (alenlist)
624 *cursorp_out = alenlist->al_cursor; /* small structure copy */
625 else if (cursorp_in)
626 *cursorp_out = *cursorp_in; /* small structure copy */
627 else
628 return(ALENLIST_FAILURE); /* no source */
629
630 return(ALENLIST_SUCCESS);
631 }
632
633 /*
634 * Return the number of bytes passed so far according to the specified cursor.
635 * If cursorp is NULL, use the alenlist's internal cursor.
636 */
637 size_t
638 alenlist_cursor_offset(alenlist_t alenlist, alenlist_cursor_t cursorp)
639 {
640 ASSERT(!alenlist || !cursorp || (alenlist == cursorp->al_alenlist));
641
642 if (cursorp == NULL) {
643 ASSERT(alenlist);
644 cursorp = &alenlist->al_cursor;
645 }
646
647 return(cursorp->al_offset);
648 }
649
650 /*
651 * Allocate and initialize an Address/Length List cursor.
652 */
653 alenlist_cursor_t
654 alenlist_cursor_create(alenlist_t alenlist, unsigned flags)
655 {
656 alenlist_cursor_t cursorp;
657
658 ASSERT(alenlist != NULL);
659 cursorp = kmem_zone_alloc(alenlist_cursor_zone, flags & AL_NOSLEEP ? VM_NOSLEEP : 0);
660 if (cursorp) {
661 INCR_COUNT(&alenlist_cursor_count);
662 alenlist_cursor_init(alenlist, 0, cursorp);
663 }
664 return(cursorp);
665 }
666
667 /*
668 * Free an Address/Length List cursor.
669 */
670 void
671 alenlist_cursor_destroy(alenlist_cursor_t cursorp)
672 {
673 DECR_COUNT(&alenlist_cursor_count);
674 kmem_zone_free(alenlist_cursor_zone, cursorp);
675 }
676
677
678 /*
679 * Fetch an address/length pair from an Address/Length List. Update
680 * the "cursor" so that next time this routine is called, we'll get
681 * the next address range. Never return a length that exceeds maxlength
682 * (if non-zero). If maxlength is a power of 2, never return a length
683 * that crosses a maxlength boundary. [This may seem strange at first,
684 * but it's what many drivers want.]
685 *
686 * Returns: SUCCESS/FAILURE
687 */
688 int
689 alenlist_get( alenlist_t alenlist, /* in: get from this list */
690 alenlist_cursor_t cursorp, /* inout: which item to get */
691 size_t maxlength, /* in: at most this length */
692 alenaddr_t *addrp, /* out: address */
693 size_t *lengthp, /* out: length */
694 unsigned flags)
695 {
696 alen_t *alenp;
697 alenlist_chunk_t chunk;
698 unsigned int index;
699 size_t bcount;
700 size_t length;
701
702 /*
703 * If no cursor explicitly specified, use the Address/Length List's
704 * internal cursor.
705 */
706 if (cursorp == NULL) {
707 if (alenlist->al_logical_size == 0)
708 return(ALENLIST_FAILURE);
709 cursorp = &alenlist->al_cursor;
710 }
711
712 chunk = cursorp->al_chunk;
713 index = cursorp->al_index;
714 bcount = cursorp->al_bcount;
715
716 ASSERT(cursorp->al_alenlist == alenlist);
717 if (cursorp->al_alenlist != alenlist)
718 return(ALENLIST_FAILURE);
719
720 alenp = &chunk->alc_pair[index];
721 length = alenp->al_length - bcount;
722
723 /* Bump up to next pair, if we're done with this pair. */
724 if (length == 0) {
725 cursorp->al_bcount = bcount = 0;
726 cursorp->al_index = index = (index + 1) % ALEN_CHUNK_SZ;
727
728 /* Bump up to next chunk, if we're done with this chunk. */
729 if (index == 0) {
730 if (cursorp->al_chunk == alenlist->al_last_chunk)
731 return(ALENLIST_FAILURE);
732 chunk = chunk->alc_next;
733 ASSERT(chunk != NULL);
734 } else {
735 /* If in last chunk, don't go beyond end. */
736 if (cursorp->al_chunk == alenlist->al_last_chunk) {
737 int last_size = alenlist->al_logical_size % ALEN_CHUNK_SZ;
738 if (last_size && (index >= last_size))
739 return(ALENLIST_FAILURE);
740 }
741 }
742
743 alenp = &chunk->alc_pair[index];
744 length = alenp->al_length;
745 }
746
747 /* Constrain what we return according to maxlength */
748 if (maxlength) {
749 size_t maxlen1 = maxlength - 1;
750
751 if ((maxlength & maxlen1) == 0) /* power of 2 */
752 maxlength -=
753 ((alenp->al_addr + cursorp->al_bcount) & maxlen1);
754
755 length = MIN(maxlength, length);
756 }
757
758 /* Update the cursor, if desired. */
759 if (!(flags & AL_LEAVE_CURSOR)) {
760 cursorp->al_bcount += length;
761 cursorp->al_chunk = chunk;
762 }
763
764 *lengthp = length;
765 *addrp = alenp->al_addr + bcount;
766
767 return(ALENLIST_SUCCESS);
768 }
769
770
771 /*
772 * Return the number of pairs in the specified Address/Length List.
773 * (For FIXED_SIZE Lists, this returns the logical size of the List,
774 * not the actual capacity of the List.)
775 */
776 int
777 alenlist_size(alenlist_t alenlist)
778 {
779 return(alenlist->al_logical_size);
780 }
781
782
783 /*
784 * Concatenate two Address/Length Lists.
785 */
786 void
787 alenlist_concat(alenlist_t from,
788 alenlist_t to)
789 {
790 struct alenlist_cursor_s cursor;
791 alenaddr_t addr;
792 size_t length;
793
794 alenlist_cursor_init(from, 0, &cursor);
795
796 while(alenlist_get(from, &cursor, (size_t)0, &addr, &length, 0) == ALENLIST_SUCCESS)
797 alenlist_append(to, addr, length, 0);
798 }
799
800 /*
801 * Create a copy of a list.
802 * (Not all attributes of the old list are cloned. For instance, if
803 * a FIXED_SIZE list is cloned, the resulting list is NOT FIXED_SIZE.)
804 */
805 alenlist_t
806 alenlist_clone(alenlist_t old_list, unsigned flags)
807 {
808 alenlist_t new_list;
809
810 new_list = alenlist_create(flags);
811 if (new_list != NULL)
812 alenlist_concat(old_list, new_list);
813
814 return(new_list);
815 }
816
817
818 /*
819 * Convert a kernel virtual address to a Physical Address/Length List.
820 */
821 alenlist_t
822 kvaddr_to_alenlist(alenlist_t alenlist, caddr_t kvaddr, size_t length, unsigned flags)
823 {
824 alenaddr_t paddr;
825 long offset;
826 size_t piece_length;
827 int created_alenlist;
828
829 if (length <=0)
830 return(NULL);
831
832 /* If caller supplied a List, use it. Otherwise, allocate one. */
833 if (alenlist == NULL) {
834 alenlist = alenlist_create(0);
835 created_alenlist = 1;
836 } else {
837 alenlist_clear(alenlist);
838 created_alenlist = 0;
839 }
840
841 paddr = kvtophys(kvaddr);
842 offset = poff(kvaddr);
843
844 /* Handle first page */
845 piece_length = MIN(NBPP - offset, length);
846 if (alenlist_append(alenlist, paddr, piece_length, flags) == ALENLIST_FAILURE)
847 goto failure;
848 length -= piece_length;
849 kvaddr += piece_length;
850
851 /* Handle middle pages */
852 while (length >= NBPP) {
853 paddr = kvtophys(kvaddr);
854 if (alenlist_append(alenlist, paddr, NBPP, flags) == ALENLIST_FAILURE)
855 goto failure;
856 length -= NBPP;
857 kvaddr += NBPP;
858 }
859
860 /* Handle last page */
861 if (length) {
862 ASSERT(length < NBPP);
863 paddr = kvtophys(kvaddr);
864 if (alenlist_append(alenlist, paddr, length, flags) == ALENLIST_FAILURE)
865 goto failure;
866 }
867
868 alenlist_cursor_init(alenlist, 0, NULL);
869 return(alenlist);
870
871 failure:
872 if (created_alenlist)
873 alenlist_destroy(alenlist);
874 return(NULL);
875 }
876
877
878 #if DEBUG
879 static void
880 alenlist_show(alenlist_t alenlist)
881 {
882 struct alenlist_cursor_s cursor;
883 alenaddr_t addr;
884 size_t length;
885 int i = 0;
886
887 alenlist_cursor_init(alenlist, 0, &cursor);
888
889 qprintf("Address/Length List@0x%x:\n", alenlist);
890 qprintf("logical size=0x%x actual size=0x%x last_chunk at 0x%x\n",
891 alenlist->al_logical_size, alenlist->al_actual_size,
892 alenlist->al_last_chunk);
893 qprintf("cursor: chunk=0x%x index=%d offset=0x%x\n",
894 alenlist->al_cursor.al_chunk,
895 alenlist->al_cursor.al_index,
896 alenlist->al_cursor.al_bcount);
897 while(alenlist_get(alenlist, &cursor, (size_t)0, &addr, &length, 0) == ALENLIST_SUCCESS)
898 qprintf("%d:\t0x%lx 0x%lx\n", ++i, addr, length);
899 }
900 #endif /* DEBUG */
901