Moved most buffer debug messages to DBG2.
[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         DBGC2 ( 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 ( ( rc = expand_buffer ( buffer, data_end ) ) != 0 )
171                         return rc;
172                 assert ( buffer->len >= data_end );
173         }
174
175         /* Find 'before' and 'after' blocks, if any */
176         before.start = before.end = 0;
177         after.start = after.end = buffer->len;
178         block.next = buffer->fill;
179         while ( get_next_free_block ( buffer, &block ) == 0 ) {
180                 if ( ( block.start < data_start ) &&
181                      ( block.start >= before.start ) )
182                         memcpy ( &before, &block, sizeof ( before ) );
183                 if ( ( block.end > data_end ) &&
184                      ( block.end <= after.end ) )
185                         memcpy ( &after, &block, sizeof ( after ) );
186         }
187
188         /* Truncate 'before' and 'after' blocks around data. */
189         if ( data_start < before.end )
190                 before.end = data_start;
191         if ( data_end > after.start )
192                 after.start = data_end;
193
194         /* Link 'after' block to 'before' block */
195         before.next = after.start;
196
197         DBGC2 ( buffer, "BUFFER %p split before [%lx,%lx) after [%lx,%lx)\n",
198                 buffer, user_to_phys ( buffer->addr, before.start ),
199                 user_to_phys ( buffer->addr, before.end ),
200                 user_to_phys ( buffer->addr, after.start ),
201                 user_to_phys ( buffer->addr, after.end ) );
202
203         /* Write back 'before' block, if any */
204         if ( before.end == 0 ) {
205                 /* No 'before' block: update buffer->fill */
206                 buffer->fill = after.start;
207                 DBGC2 ( buffer, "BUFFER %p full up to %lx\n", buffer,
208                         user_to_phys ( buffer->addr, buffer->fill ) );
209         } else {
210                 /* Write back 'before' block */
211                 store_free_block ( buffer, &before );
212         }
213
214         /* Write back 'after' block */
215         if ( after.end == buffer->len ) {
216                 /* 'After' block is the final block: update buffer->free */
217                 buffer->free = after.start;
218                 DBGC2 ( buffer, "BUFFER %p free from %lx onwards\n", buffer,
219                         user_to_phys ( buffer->addr, buffer->free ) );
220         } else {
221                 /* Write back 'after' block */
222                 store_free_block ( buffer, &after );
223         }
224
225         /* Copy data into buffer */
226         copy_to_user ( buffer->addr, data_start, data, len );
227
228         return 0;
229 }
230
231 /** Expand data buffer
232  *
233  * @v buffer            Data buffer
234  * @v new_len           New length
235  * @ret rc              Return status code
236  *
237  * Expand the data buffer to accommodate more data.  Some buffers may
238  * not support being expanded.
239  */
240 int expand_buffer ( struct buffer *buffer, size_t new_len ) {
241         int rc;
242
243         if ( new_len <= buffer->len )
244                 return 0;
245
246         DBGC ( buffer, "BUFFER %p attempting to expand from length %zx to "
247                "length %zx\n", buffer, buffer->len, new_len );
248
249         if ( ! buffer->expand ) {
250                 DBGC ( buffer, "BUFFER %p is not expandable\n", buffer );
251                 return -ENOBUFS;
252         }
253
254         if ( ( rc = buffer->expand ( buffer, new_len ) ) != 0 ) {
255                 DBGC ( buffer, "BUFFER %p could not expand: %s\n",
256                        buffer, strerror ( rc ) );
257                 return rc;
258         }
259
260         DBGC ( buffer, "BUFFER %p expanded to [%lx,%lx)\n", buffer,
261                user_to_phys ( buffer->addr, 0 ),
262                user_to_phys ( buffer->addr, buffer->len ) );
263
264         return 0;
265 }