source: mainline/uspace/lib/libblock/libblock.c@ dd2cfa7

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since dd2cfa7 was d68e4d5, checked in by Jakub Jermar <jakub@…>, 16 years ago

Make the libblock cache behave more like a cache and fix some bugs
present in the previously unused code paths.
  • Property mode set to 100644
File size: 14.6 KB
Line 
1/*
2 * Copyright (c) 2008 Jakub Jermar
3 * Copyright (c) 2008 Martin Decky
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * - Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * - The name of the author may not be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/** @addtogroup libblock
31 * @{
32 */
33/**
34 * @file
35 * @brief
36 */
37
38#include "libblock.h"
39#include "../../srv/vfs/vfs.h"
40#include <ipc/devmap.h>
41#include <ipc/bd.h>
42#include <ipc/services.h>
43#include <errno.h>
44#include <sys/mman.h>
45#include <async.h>
46#include <ipc/ipc.h>
47#include <as.h>
48#include <assert.h>
49#include <fibril_sync.h>
50#include <adt/list.h>
51#include <adt/hash_table.h>
52#include <mem.h>
53
54/** Lock protecting the device connection list */
55static FIBRIL_MUTEX_INITIALIZE(dcl_lock);
56/** Device connection list head. */
57static LIST_INITIALIZE(dcl_head);
58
59#define CACHE_BUCKETS_LOG2 10
60#define CACHE_BUCKETS (1 << CACHE_BUCKETS_LOG2)
61
62typedef struct {
63 fibril_mutex_t lock;
64 size_t block_size; /**< Block size. */
65 unsigned block_count; /**< Total number of blocks. */
66 unsigned blocks_cached; /**< Number of cached blocks. */
67 hash_table_t block_hash;
68 link_t free_head;
69 enum cache_mode mode;
70} cache_t;
71
72typedef struct {
73 link_t link;
74 dev_handle_t dev_handle;
75 int dev_phone;
76 fibril_mutex_t com_area_lock;
77 void *com_area;
78 size_t com_size;
79 void *bb_buf;
80 off_t bb_off;
81 size_t bb_size;
82 cache_t *cache;
83} devcon_t;
84
85static int read_block(devcon_t *devcon, bn_t boff, size_t block_size);
86static int write_block(devcon_t *devcon, bn_t boff, size_t block_size);
87
88static devcon_t *devcon_search(dev_handle_t dev_handle)
89{
90 link_t *cur;
91
92 fibril_mutex_lock(&dcl_lock);
93 for (cur = dcl_head.next; cur != &dcl_head; cur = cur->next) {
94 devcon_t *devcon = list_get_instance(cur, devcon_t, link);
95 if (devcon->dev_handle == dev_handle) {
96 fibril_mutex_unlock(&dcl_lock);
97 return devcon;
98 }
99 }
100 fibril_mutex_unlock(&dcl_lock);
101 return NULL;
102}
103
104static int devcon_add(dev_handle_t dev_handle, int dev_phone, void *com_area,
105 size_t com_size)
106{
107 link_t *cur;
108 devcon_t *devcon;
109
110 devcon = malloc(sizeof(devcon_t));
111 if (!devcon)
112 return ENOMEM;
113
114 link_initialize(&devcon->link);
115 devcon->dev_handle = dev_handle;
116 devcon->dev_phone = dev_phone;
117 fibril_mutex_initialize(&devcon->com_area_lock);
118 devcon->com_area = com_area;
119 devcon->com_size = com_size;
120 devcon->bb_buf = NULL;
121 devcon->bb_off = 0;
122 devcon->bb_size = 0;
123 devcon->cache = NULL;
124
125 fibril_mutex_lock(&dcl_lock);
126 for (cur = dcl_head.next; cur != &dcl_head; cur = cur->next) {
127 devcon_t *d = list_get_instance(cur, devcon_t, link);
128 if (d->dev_handle == dev_handle) {
129 fibril_mutex_unlock(&dcl_lock);
130 free(devcon);
131 return EEXIST;
132 }
133 }
134 list_append(&devcon->link, &dcl_head);
135 fibril_mutex_unlock(&dcl_lock);
136 return EOK;
137}
138
139static void devcon_remove(devcon_t *devcon)
140{
141 fibril_mutex_lock(&dcl_lock);
142 list_remove(&devcon->link);
143 fibril_mutex_unlock(&dcl_lock);
144}
145
146int block_init(dev_handle_t dev_handle, size_t com_size)
147{
148 int rc;
149 int dev_phone;
150 void *com_area;
151
152 com_area = mmap(NULL, com_size, PROTO_READ | PROTO_WRITE,
153 MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
154 if (!com_area) {
155 return ENOMEM;
156 }
157
158 dev_phone = devmap_device_connect(dev_handle, IPC_FLAG_BLOCKING);
159 if (dev_phone < 0) {
160 munmap(com_area, com_size);
161 return dev_phone;
162 }
163
164 rc = ipc_share_out_start(dev_phone, com_area,
165 AS_AREA_READ | AS_AREA_WRITE);
166 if (rc != EOK) {
167 munmap(com_area, com_size);
168 ipc_hangup(dev_phone);
169 return rc;
170 }
171
172 rc = devcon_add(dev_handle, dev_phone, com_area, com_size);
173 if (rc != EOK) {
174 munmap(com_area, com_size);
175 ipc_hangup(dev_phone);
176 return rc;
177 }
178
179 return EOK;
180}
181
182void block_fini(dev_handle_t dev_handle)
183{
184 devcon_t *devcon = devcon_search(dev_handle);
185 assert(devcon);
186
187 devcon_remove(devcon);
188
189 if (devcon->bb_buf)
190 free(devcon->bb_buf);
191
192 if (devcon->cache) {
193 hash_table_destroy(&devcon->cache->block_hash);
194 free(devcon->cache);
195 }
196
197 munmap(devcon->com_area, devcon->com_size);
198 ipc_hangup(devcon->dev_phone);
199
200 free(devcon);
201}
202
203int block_bb_read(dev_handle_t dev_handle, off_t off, size_t size)
204{
205 void *bb_buf;
206 int rc;
207
208 devcon_t *devcon = devcon_search(dev_handle);
209 if (!devcon)
210 return ENOENT;
211 if (devcon->bb_buf)
212 return EEXIST;
213 bb_buf = malloc(size);
214 if (!bb_buf)
215 return ENOMEM;
216
217 fibril_mutex_lock(&devcon->com_area_lock);
218 rc = read_block(devcon, 0, size);
219 if (rc != EOK) {
220 fibril_mutex_unlock(&devcon->com_area_lock);
221 free(bb_buf);
222 return rc;
223 }
224 memcpy(bb_buf, devcon->com_area, size);
225 fibril_mutex_unlock(&devcon->com_area_lock);
226
227 devcon->bb_buf = bb_buf;
228 devcon->bb_off = off;
229 devcon->bb_size = size;
230
231 return EOK;
232}
233
234void *block_bb_get(dev_handle_t dev_handle)
235{
236 devcon_t *devcon = devcon_search(dev_handle);
237 assert(devcon);
238 return devcon->bb_buf;
239}
240
241static hash_index_t cache_hash(unsigned long *key)
242{
243 return *key & (CACHE_BUCKETS - 1);
244}
245
246static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item)
247{
248 block_t *b = hash_table_get_instance(item, block_t, hash_link);
249 return b->boff == *key;
250}
251
252static void cache_remove_callback(link_t *item)
253{
254}
255
256static hash_table_operations_t cache_ops = {
257 .hash = cache_hash,
258 .compare = cache_compare,
259 .remove_callback = cache_remove_callback
260};
261
262int block_cache_init(dev_handle_t dev_handle, size_t size, unsigned blocks,
263 enum cache_mode mode)
264{
265 devcon_t *devcon = devcon_search(dev_handle);
266 cache_t *cache;
267 if (!devcon)
268 return ENOENT;
269 if (devcon->cache)
270 return EEXIST;
271 cache = malloc(sizeof(cache_t));
272 if (!cache)
273 return ENOMEM;
274
275 fibril_mutex_initialize(&cache->lock);
276 list_initialize(&cache->free_head);
277 cache->block_size = size;
278 cache->block_count = blocks;
279 cache->blocks_cached = 0;
280 cache->mode = mode;
281
282 if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 1,
283 &cache_ops)) {
284 free(cache);
285 return ENOMEM;
286 }
287
288 devcon->cache = cache;
289 return EOK;
290}
291
292#define CACHE_LO_WATERMARK 10
293#define CACHE_HI_WATERMARK 20
294static bool cache_can_grow(cache_t *cache)
295{
296 if (cache->blocks_cached < CACHE_LO_WATERMARK)
297 return true;
298 if (!list_empty(&cache->free_head))
299 return false;
300 return true;
301}
302
303static void block_initialize(block_t *b)
304{
305 fibril_mutex_initialize(&b->lock);
306 b->refcnt = 1;
307 b->dirty = false;
308 fibril_rwlock_initialize(&b->contents_lock);
309 link_initialize(&b->free_link);
310 link_initialize(&b->hash_link);
311}
312
313/** Instantiate a block in memory and get a reference to it.
314 *
315 * @param dev_handle Device handle of the block device.
316 * @param boff Block offset.
317 * @param flags If BLOCK_FLAGS_NOREAD is specified, block_get()
318 * will not read the contents of the block from the
319 * device.
320 *
321 * @return Block structure.
322 */
323block_t *block_get(dev_handle_t dev_handle, bn_t boff, int flags)
324{
325 devcon_t *devcon;
326 cache_t *cache;
327 block_t *b;
328 link_t *l;
329 unsigned long key = boff;
330 bn_t oboff;
331
332 devcon = devcon_search(dev_handle);
333
334 assert(devcon);
335 assert(devcon->cache);
336
337 cache = devcon->cache;
338 fibril_mutex_lock(&cache->lock);
339 l = hash_table_find(&cache->block_hash, &key);
340 if (l) {
341 /*
342 * We found the block in the cache.
343 */
344 b = hash_table_get_instance(l, block_t, hash_link);
345 fibril_mutex_lock(&b->lock);
346 if (b->refcnt++ == 0)
347 list_remove(&b->free_link);
348 fibril_mutex_unlock(&b->lock);
349 fibril_mutex_unlock(&cache->lock);
350 } else {
351 /*
352 * The block was not found in the cache.
353 */
354 int rc;
355 bool sync = false;
356
357 if (cache_can_grow(cache)) {
358 /*
359 * We can grow the cache by allocating new blocks.
360 * Should the allocation fail, we fail over and try to
361 * recycle a block from the cache.
362 */
363 b = malloc(sizeof(block_t));
364 if (!b)
365 goto recycle;
366 b->data = malloc(cache->block_size);
367 if (!b->data) {
368 free(b);
369 goto recycle;
370 }
371 cache->blocks_cached++;
372 } else {
373 /*
374 * Try to recycle a block from the free list.
375 */
376 unsigned long temp_key;
377recycle:
378 assert(!list_empty(&cache->free_head));
379 l = cache->free_head.next;
380 list_remove(l);
381 b = list_get_instance(l, block_t, free_link);
382 sync = b->dirty;
383 oboff = b->boff;
384 temp_key = b->boff;
385 hash_table_remove(&cache->block_hash, &temp_key, 1);
386 }
387
388 block_initialize(b);
389 b->dev_handle = dev_handle;
390 b->size = cache->block_size;
391 b->boff = boff;
392 hash_table_insert(&cache->block_hash, &key, &b->hash_link);
393
394 /*
395 * Lock the block before releasing the cache lock. Thus we don't
396 * kill concurent operations on the cache while doing I/O on the
397 * block.
398 */
399 fibril_mutex_lock(&b->lock);
400 fibril_mutex_unlock(&cache->lock);
401
402 if (sync) {
403 /*
404 * The block is dirty and needs to be written back to
405 * the device before we can read in the new contents.
406 */
407 fibril_mutex_lock(&devcon->com_area_lock);
408 memcpy(devcon->com_area, b->data, b->size);
409 rc = write_block(devcon, oboff, cache->block_size);
410 assert(rc == EOK);
411 fibril_mutex_unlock(&devcon->com_area_lock);
412 }
413 if (!(flags & BLOCK_FLAGS_NOREAD)) {
414 /*
415 * The block contains old or no data. We need to read
416 * the new contents from the device.
417 */
418 fibril_mutex_lock(&devcon->com_area_lock);
419 rc = read_block(devcon, b->boff, cache->block_size);
420 assert(rc == EOK);
421 memcpy(b->data, devcon->com_area, cache->block_size);
422 fibril_mutex_unlock(&devcon->com_area_lock);
423 }
424
425 fibril_mutex_unlock(&b->lock);
426 }
427 return b;
428}
429
430/** Release a reference to a block.
431 *
432 * If the last reference is dropped, the block is put on the free list.
433 *
434 * @param block Block of which a reference is to be released.
435 */
436void block_put(block_t *block)
437{
438 devcon_t *devcon = devcon_search(block->dev_handle);
439 cache_t *cache;
440 int rc;
441
442 assert(devcon);
443 assert(devcon->cache);
444
445 cache = devcon->cache;
446 fibril_mutex_lock(&cache->lock);
447 fibril_mutex_lock(&block->lock);
448 if (!--block->refcnt) {
449 /*
450 * Last reference to the block was dropped. Either free the
451 * block or put it on the free list.
452 */
453 if (cache->blocks_cached > CACHE_HI_WATERMARK) {
454 /*
455 * Currently there are too many cached blocks.
456 */
457 if (block->dirty) {
458 fibril_mutex_lock(&devcon->com_area_lock);
459 memcpy(devcon->com_area, block->data,
460 block->size);
461 rc = write_block(devcon, block->boff,
462 block->size);
463 assert(rc == EOK);
464 fibril_mutex_unlock(&devcon->com_area_lock);
465 }
466 /*
467 * Take the block out of the cache and free it.
468 */
469 unsigned long key = block->boff;
470 hash_table_remove(&cache->block_hash, &key, 1);
471 free(block);
472 free(block->data);
473 cache->blocks_cached--;
474 fibril_mutex_unlock(&cache->lock);
475 return;
476 }
477 /*
478 * Put the block on the free list.
479 */
480 list_append(&block->free_link, &cache->free_head);
481 if (cache->mode != CACHE_MODE_WB && block->dirty) {
482 fibril_mutex_lock(&devcon->com_area_lock);
483 memcpy(devcon->com_area, block->data, block->size);
484 rc = write_block(devcon, block->boff, block->size);
485 assert(rc == EOK);
486 fibril_mutex_unlock(&devcon->com_area_lock);
487
488 block->dirty = false;
489 }
490 }
491 fibril_mutex_unlock(&block->lock);
492 fibril_mutex_unlock(&cache->lock);
493}
494
495/** Read sequential data from a block device.
496 *
497 * @param dev_handle Device handle of the block device.
498 * @param bufpos Pointer to the first unread valid offset within the
499 * communication buffer.
500 * @param buflen Pointer to the number of unread bytes that are ready in
501 * the communication buffer.
502 * @param pos Device position to be read.
503 * @param dst Destination buffer.
504 * @param size Size of the destination buffer.
505 * @param block_size Block size to be used for the transfer.
506 *
507 * @return EOK on success or a negative return code on failure.
508 */
509int block_seqread(dev_handle_t dev_handle, off_t *bufpos, size_t *buflen,
510 off_t *pos, void *dst, size_t size, size_t block_size)
511{
512 off_t offset = 0;
513 size_t left = size;
514 devcon_t *devcon = devcon_search(dev_handle);
515 assert(devcon);
516
517 fibril_mutex_lock(&devcon->com_area_lock);
518 while (left > 0) {
519 size_t rd;
520
521 if (*bufpos + left < *buflen)
522 rd = left;
523 else
524 rd = *buflen - *bufpos;
525
526 if (rd > 0) {
527 /*
528 * Copy the contents of the communication buffer to the
529 * destination buffer.
530 */
531 memcpy(dst + offset, devcon->com_area + *bufpos, rd);
532 offset += rd;
533 *bufpos += rd;
534 *pos += rd;
535 left -= rd;
536 }
537
538 if (*bufpos == (off_t) *buflen) {
539 /* Refill the communication buffer with a new block. */
540 int rc;
541
542 rc = read_block(devcon, *pos / block_size, block_size);
543 if (rc != EOK) {
544 fibril_mutex_unlock(&devcon->com_area_lock);
545 return rc;
546 }
547
548 *bufpos = 0;
549 *buflen = block_size;
550 }
551 }
552 fibril_mutex_unlock(&devcon->com_area_lock);
553
554 return EOK;
555}
556
557/** Read block from block device.
558 *
559 * @param devcon Device connection.
560 * @param boff Block index.
561 * @param block_size Block size.
562 * @param src Buffer for storing the data.
563 *
564 * @return EOK on success or negative error code on failure.
565 */
566static int read_block(devcon_t *devcon, bn_t boff, size_t block_size)
567{
568 ipcarg_t retval;
569 int rc;
570
571 assert(devcon);
572 rc = async_req_2_1(devcon->dev_phone, BD_READ_BLOCK, boff, block_size,
573 &retval);
574 if ((rc != EOK) || (retval != EOK))
575 return (rc != EOK ? rc : (int) retval);
576
577 return EOK;
578}
579
580/** Write block to block device.
581 *
582 * @param devcon Device connection.
583 * @param boff Block index.
584 * @param block_size Block size.
585 * @param src Buffer containing the data to write.
586 *
587 * @return EOK on success or negative error code on failure.
588 */
589static int write_block(devcon_t *devcon, bn_t boff, size_t block_size)
590{
591 ipcarg_t retval;
592 int rc;
593
594 assert(devcon);
595 rc = async_req_2_1(devcon->dev_phone, BD_WRITE_BLOCK, boff, block_size,
596 &retval);
597 if ((rc != EOK) || (retval != EOK))
598 return (rc != EOK ? rc : (int) retval);
599
600 return EOK;
601}
602
603/** @}
604 */
Note: See TracBrowser for help on using the repository browser.