c382b5fe2362d9644d8a6d2bce14af9f09ebe00b
[people/xl0/gpxe.git] / src / core / buffer.c
1 /*
2  * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17  */
18
19 #include <stddef.h>
20 #include <string.h>
21 #include <errno.h>
22 #include <assert.h>
23 #include <gpxe/uaccess.h>
24 #include <gpxe/buffer.h>
25
26 /** @file
27  *
28  * Buffer internals.
29  *
30  * A buffer consists of a single, contiguous area of memory, some of
31  * which is "filled" and the remainder of which is "free".  The
32  * "filled" and "free" spaces are not necessarily contiguous.
33  *
34  * At the start of a buffer's life, it consists of a single free
35  * space.  As data is added to the buffer via fill_buffer(), this free
36  * space decreases and can become fragmented.
37  *
38  * Each free block within a buffer (except the last) starts with a @c
39  * struct @c buffer_free_block.  This describes the size of the free
40  * block, and the offset to the next free block.
41  *
42  * We cannot simply start every free block (including the last) with a
43  * descriptor, because it is conceivable that we will, at some point,
44  * encounter a situation in which the final free block of a buffer is
45  * too small to contain a descriptor.  Consider a protocol with a
46  * blocksize of 512 downloading a 1025-byte file into a 1025-byte
47  * buffer.  Suppose that the first two blocks are received; we have
48  * now filled 1024 of the 1025 bytes in the buffer, and our only free
49  * block consists of the 1025th byte.
50  * 
51  * Note that the rather convoluted way of manipulating the buffer
52  * descriptors (using copy_{to,from}_user rather than straightforward
53  * pointers) is needed to cope with operation as a PXE stack, when we
54  * may be running in real mode or 16-bit protected mode, and therefore
55  * cannot directly access arbitrary areas of memory using simple
56  * pointers.
57  *
58  */
59
60 /**
61  * A free block descriptor
62  *
63  * This is the data structure that is found at the start of a free
64  * block within a data buffer.
65  */
66 struct buffer_free_block {
67         /** Starting offset of the free block */
68         size_t start;
69         /** Ending offset of the free block */
70         size_t end;
71         /** Offset of next free block */
72         size_t next;
73 };
74
75 /**
76  * Get next free block within the buffer
77  *
78  * @v buffer            Data buffer
79  * @v block             Previous free block descriptor
80  * @ret block           Next free block descriptor
81  * @ret rc              Return status code
82  *
83  * Set @c block->next=buffer->fill before first call to
84  * get_next_free_block().
85  */
86 static int get_next_free_block ( struct buffer *buffer,
87                                  struct buffer_free_block *block ) {
88
89         /* Check for end of buffer */
90         if ( block->next >= buffer->len )
91                 return -ENOENT;
92
93         /* Move to next block */
94         block->start = block->next;
95         if ( block->start >= buffer->free ) {
96                 /* Final block; no in-band descriptor */
97                 block->next = block->end = buffer->len;
98         } else {
99                 /* Retrieve block descriptor */
100                 copy_from_user ( block, buffer->addr, block->start,
101                                  sizeof ( *block ) );
102         }
103
104         return 0;
105 }
106
107 /**
108  * Write free block descriptor back to buffer
109  *
110  * @v buffer            Data buffer
111  * @v block             Free block descriptor
112  */
113 static void store_free_block ( struct buffer *buffer,
114                                struct buffer_free_block *block ) {
115         size_t free_block_size = ( block->end - block->start );
116
117         assert ( free_block_size >= sizeof ( *block ) );
118         copy_to_user ( buffer->addr, block->start, block, sizeof ( *block ) );
119 }
120
121 /**
122  * Write data into a buffer
123  *
124  * @v buffer            Data buffer
125  * @v data              Data to be written
126  * @v offset            Offset within the buffer at which to write the data
127  * @v len               Length of data to be written
128  * @ret rc              Return status code
129  *
130  * Writes a block of data into the buffer.  The block need not be
131  * aligned to any particular boundary, or be of any particular size,
132  * and it may overlap blocks already in the buffer (i.e. duplicate
133  * calls to fill_buffer() are explicitly permitted).
134  *
135  * @c buffer->fill will be updated to indicate the fill level of the
136  * buffer, i.e. the offset to the first gap within the buffer.  If the
137  * filesize is known (e.g. as with the SLAM protocol), you can test
138  * for end-of-file by checking for @c buffer->fill==filesize.  If the
139  * filesize is not known, but there is a well-defined end-of-file test
140  * (e.g. as with the TFTP protocol), you can read @c buffer->fill to
141  * determine the final filesize.  If blocks are known to be delivered
142  * in a strictly sequential order with no packet loss or duplication,
143  * then you can pass in @c offset==buffer->fill.
144  *
145  * @b NOTE: It is the caller's responsibility to ensure that the
146  * boundaries between data blocks are more than @c sizeof(struct @c
147  * buffer_free_block) apart.  If this condition is not satisfied, data
148  * corruption will occur.
149  *
150  * In practice this is not a problem.  Callers of fill_buffer() will
151  * be download protocols such as TFTP, and very few protocols have a
152  * block size smaller than @c sizeof(struct @c buffer_free_block).
153  *
154  */
155 int fill_buffer ( struct buffer *buffer, const void *data,
156                   size_t offset, size_t len ) {
157         struct buffer_free_block block, before, after;
158         size_t data_start = offset;
159         size_t data_end = ( data_start + len );
160         int rc;
161
162         DBGC ( buffer, "BUFFER %p [%lx,%lx) filling portion [%lx,%lx)\n",
163                buffer, user_to_phys ( buffer->addr, 0 ),
164                user_to_phys ( buffer->addr, buffer->len ),
165                user_to_phys ( buffer->addr, data_start ),
166                user_to_phys ( buffer->addr, data_end ) );
167
168         /* Check that block fits within buffer, expand if necessary */
169         if ( data_end > buffer->len ) {
170                 if ( ! buffer->expand ) {
171                         DBGC ( buffer, "BUFFER %p not expandable\n", buffer );
172                         return -ENOBUFS;
173                 }
174                 if ( ( rc = buffer->expand ( buffer, data_end ) ) != 0 ) {
175                         DBGC ( buffer, "BUFFER %p could not expand :%s\n",
176                                buffer, strerror ( rc ) );
177                         return rc;
178                 }
179                 DBGC ( buffer, "BUFFER %p expanded to [%lx,%lx)\n", buffer,
180                        user_to_phys ( buffer->addr, 0 ),
181                        user_to_phys ( buffer->addr, buffer->len ) );
182                 assert ( buffer->len >= data_end );
183         }
184
185         /* Find 'before' and 'after' blocks, if any */
186         before.start = before.end = 0;
187         after.start = after.end = buffer->len;
188         block.next = buffer->fill;
189         while ( get_next_free_block ( buffer, &block ) == 0 ) {
190                 if ( ( block.start < data_start ) &&
191                      ( block.start >= before.start ) )
192                         memcpy ( &before, &block, sizeof ( before ) );
193                 if ( ( block.end > data_end ) &&
194                      ( block.end <= after.end ) )
195                         memcpy ( &after, &block, sizeof ( after ) );
196         }
197
198         /* Truncate 'before' and 'after' blocks around data. */
199         if ( data_start < before.end )
200                 before.end = data_start;
201         if ( data_end > after.start )
202                 after.start = data_end;
203
204         /* Link 'after' block to 'before' block */
205         before.next = after.start;
206
207         DBGC ( buffer, "BUFFER %p split before [%lx,%lx) after [%lx,%lx)\n",
208                buffer, user_to_phys ( buffer->addr, before.start ),
209                user_to_phys ( buffer->addr, before.end ),
210                user_to_phys ( buffer->addr, after.start ),
211                user_to_phys ( buffer->addr, after.end ) );
212
213         /* Write back 'before' block, if any */
214         if ( before.end == 0 ) {
215                 /* No 'before' block: update buffer->fill */
216                 buffer->fill = after.start;
217                 DBGC ( buffer, "BUFFER %p full up to %lx\n", buffer,
218                        user_to_phys ( buffer->addr, buffer->fill ) );
219         } else {
220                 /* Write back 'before' block */
221                 store_free_block ( buffer, &before );
222         }
223
224         /* Write back 'after' block */
225         if ( after.end == buffer->len ) {
226                 /* 'After' block is the final block: update buffer->free */
227                 buffer->free = after.start;
228                 DBGC ( buffer, "BUFFER %p free from %lx onwards\n", buffer,
229                        user_to_phys ( buffer->addr, buffer->free ) );
230         } else {
231                 /* Write back 'after' block */
232                 store_free_block ( buffer, &after );
233         }
234
235         /* Copy data into buffer */
236         copy_to_user ( buffer->addr, data_start, data, len );
237
238         return 0;
239 }