171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher/* 271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * Create a squashfs filesystem. This is a highly compressed read only 371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * filesystem. 471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * 52511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher * Copyright (c) 2013, 2014 671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * Phillip Lougher <phillip@squashfs.org.uk> 771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * 871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * This program is free software; you can redistribute it and/or 971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * modify it under the terms of the GNU General Public License 1071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * as published by the Free Software Foundation; either version 2, 1171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * or (at your option) any later version. 1271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * 1371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * This program is distributed in the hope that it will be useful, 1471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * but WITHOUT ANY WARRANTY; without even the implied warranty of 1571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * GNU General Public License for more details. 1771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * 1871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * You should have received a copy of the GNU General Public License 1971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * along with this program; if not, write to the Free Software 2071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 2171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * 2271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * caches-queues-lists.c 2371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher */ 2471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 2571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#include <pthread.h> 2671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#include <stdlib.h> 2771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#include <string.h> 28db888d833db8f57edb0e801fad4ebb22db671296Phillip Lougher#include <stdio.h> 2971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 3071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#include "error.h" 3171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#include "caches-queues-lists.h" 3271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 3371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougherextern int add_overflow(int, int); 3471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougherextern int multiply_overflow(int, int); 3571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 3671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#define TRUE 1 3771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher#define FALSE 0 3871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 3971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougherstruct queue *queue_init(int size) 4071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 4171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher struct queue *queue = malloc(sizeof(struct queue)); 4271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 4371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(queue == NULL) 4471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher MEM_ERROR(); 4571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 4671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(add_overflow(size, 1) || 4771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher multiply_overflow(size + 1, sizeof(void *))) 4871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher BAD_ERROR("Size too large in queue_init\n"); 4971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 5071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher queue->data = malloc(sizeof(void *) * (size + 1)); 5171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(queue->data == NULL) 5271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher MEM_ERROR(); 5371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 5471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher queue->size = size + 1; 5571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher queue->readp = queue->writep = 0; 5671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_init(&queue->mutex, NULL); 5771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_init(&queue->empty, NULL); 5871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_init(&queue->full, NULL); 5971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 6071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher return queue; 6171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 6271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 6371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 6471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Loughervoid queue_put(struct queue *queue, void *data) 6571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 6671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher int nextp; 6771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 6871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 6971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_lock(&queue->mutex); 7071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 7171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher while((nextp = (queue->writep + 1) % queue->size) == queue->readp) 7271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_wait(&queue->full, &queue->mutex); 7371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 7471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher queue->data[queue->writep] = data; 7571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher queue->writep = nextp; 7671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_signal(&queue->empty); 7771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_pop(1); 7871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 7971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 8071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 8171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Loughervoid *queue_get(struct queue *queue) 8271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 8371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher void *data; 8471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 8571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 8671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_lock(&queue->mutex); 8771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 8871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher while(queue->readp == queue->writep) 8971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_wait(&queue->empty, &queue->mutex); 9071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 9171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher data = queue->data[queue->readp]; 9271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher queue->readp = (queue->readp + 1) % queue->size; 9371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_signal(&queue->full); 9471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_pop(1); 9571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 9671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher return data; 9771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 9871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 9971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 100e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougherint queue_empty(struct queue *queue) 101e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher{ 102e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher int empty; 103e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher 104e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 105e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher pthread_mutex_lock(&queue->mutex); 106e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher 107e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher empty = queue->readp == queue->writep; 108e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher 109e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher pthread_cleanup_pop(1); 110e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher 111e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher return empty; 112e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher} 113e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher 114e57c3b5840076959cffd493ba4053007c86161f5Phillip Lougher 1152511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Loughervoid queue_flush(struct queue *queue) 1162511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher{ 1172511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 1182511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher pthread_mutex_lock(&queue->mutex); 1192511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher 1202511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher queue->readp = queue->writep; 1212511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher 1222511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher pthread_cleanup_pop(1); 1232511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher} 1242511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher 1252511927d1c835f6b3a3a8a91bfb4229c665a3554Phillip Lougher 1267538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Loughervoid dump_queue(struct queue *queue) 1277538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher{ 1287538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 1297538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher pthread_mutex_lock(&queue->mutex); 1307538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher 131fb78d2c217a087e5d53d543f335af0a2ddce5759Phillip Lougher printf("\tMax size %d, size %d%s\n", queue->size - 1, 1327538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher queue->readp <= queue->writep ? queue->writep - queue->readp : 1337538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher queue->size - queue->readp + queue->writep, 1347538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher queue->readp == queue->writep ? " (EMPTY)" : 1357538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher ((queue->writep + 1) % queue->size) == queue->readp ? 1367538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher " (FULL)" : ""); 1377538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher 1387538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher pthread_cleanup_pop(1); 1397538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher} 1407538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher 1417538d74f6fbefc11f20fe33ab75d5f197b2dee5cPhillip Lougher 142fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher/* define seq queue hash tables */ 14352c51f6f57536c72f2af0a77b4e67d378391327cPhillip Lougher#define CALCULATE_SEQ_HASH(N) CALCULATE_HASH(N) 144fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 145fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher/* Called with the seq queue mutex held */ 146137dcfcc5368ae9c78b4a8a7fb780dda21583036Phillip LougherINSERT_HASH_TABLE(seq, struct seq_queue, CALCULATE_SEQ_HASH, sequence, seq) 147fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 148fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher/* Called with the cache mutex held */ 149137dcfcc5368ae9c78b4a8a7fb780dda21583036Phillip LougherREMOVE_HASH_TABLE(seq, struct seq_queue, CALCULATE_SEQ_HASH, sequence, seq); 150fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 151fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougherstatic unsigned int sequence = 0; 152fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 153fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 154fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougherstruct seq_queue *seq_queue_init() 155fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher{ 156fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher struct seq_queue *queue = malloc(sizeof(struct seq_queue)); 157fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher if(queue == NULL) 158fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher MEM_ERROR(); 159fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 160fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher memset(queue, 0, sizeof(struct seq_queue)); 161fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 162fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_mutex_init(&queue->mutex, NULL); 163fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cond_init(&queue->wait, NULL); 164fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 165fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher return queue; 166fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher} 167fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 168fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 169fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Loughervoid seq_queue_put(struct seq_queue *queue, struct file_buffer *entry) 170fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher{ 171fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 172fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_mutex_lock(&queue->mutex); 173fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 174fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher insert_seq_hash_table(queue, entry); 175fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 176fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher if(entry->fragment) 177fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher queue->fragment_count ++; 178fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher else 179fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher queue->block_count ++; 180fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 181fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher if(entry->sequence == sequence) 182fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cond_signal(&queue->wait); 183fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 184fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cleanup_pop(1); 185fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher} 186fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 187fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 188fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougherstruct file_buffer *seq_queue_get(struct seq_queue *queue) 189fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher{ 190fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher /* 191fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher * Look-up buffer matching sequence in the queue, if found return 192fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher * it, otherwise wait until it arrives 193fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher */ 194fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher int hash = CALCULATE_SEQ_HASH(sequence); 195fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher struct file_buffer *entry; 196fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 197fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 198fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_mutex_lock(&queue->mutex); 199fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 200fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher while(1) { 201fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher for(entry = queue->hash_table[hash]; entry; 2025c7ef8cff989edfeb85a87f9f59c827c63001d0dPhillip Lougher entry = entry->seq_next) 203fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher if(entry->sequence == sequence) 204fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher break; 205fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 206fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher if(entry) { 207fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher /* 208fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher * found the buffer in the queue, decrement the 209fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher * appropriate count, and remove from hash list 210fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher */ 211fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher if(entry->fragment) 212fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher queue->fragment_count --; 213fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher else 214fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher queue->block_count --; 215fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 216fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher remove_seq_hash_table(queue, entry); 217fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 218fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher sequence ++; 219fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 220fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher break; 221fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher } 222fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 223fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher /* entry not found, wait for it to arrive */ 224fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cond_wait(&queue->wait, &queue->mutex); 225fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher } 226fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 227fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher pthread_cleanup_pop(1); 228fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 229fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher return entry; 230fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher} 231fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 232fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher 233b9929819ee40be51923a4bee41aafb279313f4a3Phillip Loughervoid seq_queue_flush(struct seq_queue *queue) 234b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher{ 235b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher int i; 236b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher 237b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 238b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher pthread_mutex_lock(&queue->mutex); 239b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher 240b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher for(i = 0; i < HASH_SIZE; i++) 241b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher queue->hash_table[i] = NULL; 242b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher 243b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher queue->fragment_count = queue->block_count = 0; 244b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher 245b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher pthread_cleanup_pop(1); 246b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher} 247b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher 248b9929819ee40be51923a4bee41aafb279313f4a3Phillip Lougher 24940e1876a205a36d4b725a1b6db8a71757190d17bPhillip Loughervoid dump_seq_queue(struct seq_queue *queue, int fragment_queue) 25040e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher{ 25140e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher int size; 25240e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher 25340e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &queue->mutex); 25440e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher pthread_mutex_lock(&queue->mutex); 25540e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher 25640e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher size = fragment_queue ? queue->fragment_count : queue->block_count; 25740e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher 258fb78d2c217a087e5d53d543f335af0a2ddce5759Phillip Lougher printf("\tMax size unlimited, size %d%s\n", size, 25940e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher size == 0 ? " (EMPTY)" : ""); 26040e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher 26140e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher pthread_cleanup_pop(1); 26240e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher} 26340e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher 26440e1876a205a36d4b725a1b6db8a71757190d17bPhillip Lougher 265fcd941550c13b9c7158b3164f29c4e00dbfda99cPhillip Lougher/* define cache hash tables */ 26652c51f6f57536c72f2af0a77b4e67d378391327cPhillip Lougher#define CALCULATE_CACHE_HASH(N) CALCULATE_HASH(llabs(N)) 26771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 26871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher/* Called with the cache mutex held */ 269137dcfcc5368ae9c78b4a8a7fb780dda21583036Phillip LougherINSERT_HASH_TABLE(cache, struct cache, CALCULATE_CACHE_HASH, index, hash) 27071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 27171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher/* Called with the cache mutex held */ 272137dcfcc5368ae9c78b4a8a7fb780dda21583036Phillip LougherREMOVE_HASH_TABLE(cache, struct cache, CALCULATE_CACHE_HASH, index, hash); 27371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 27411cb5e533794bf0b6ba25c49abc527d48ddfb183Phillip Lougher/* define cache free list */ 27511cb5e533794bf0b6ba25c49abc527d48ddfb183Phillip Lougher 27671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher/* Called with the cache mutex held */ 27771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip LougherINSERT_LIST(free, struct file_buffer) 27871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 27971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher/* Called with the cache mutex held */ 28071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip LougherREMOVE_LIST(free, struct file_buffer) 28171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 28271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 283316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougherstruct cache *cache_init(int buffer_size, int max_buffers, int noshrink_lookup, 284316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher int first_freelist) 28571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 28671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher struct cache *cache = malloc(sizeof(struct cache)); 28771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 28871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(cache == NULL) 28971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher MEM_ERROR(); 29071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 29171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher cache->max_buffers = max_buffers; 29271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher cache->buffer_size = buffer_size; 29371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher cache->count = 0; 2947a241a44cb40422c2f59e47e50c866ff78356b6cPhillip Lougher cache->used = 0; 29571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher cache->free_list = NULL; 296c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher 297c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher /* 298316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * The cache will grow up to max_buffers in size in response to 299316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * an increase in readhead/number of buffers in flight. But 300316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * once the outstanding buffers gets returned, we can either elect 301316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * to shrink the cache, or to put the freed blocks onto a free list. 302316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * 303316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * For the caches where we want to do lookup (fragment/writer), 304316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * a don't shrink policy is best, for the reader cache it 305316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * makes no sense to keep buffers around longer than necessary as 306316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * we don't do any lookup on those blocks. 307316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher */ 308316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher cache->noshrink_lookup = noshrink_lookup; 309316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 310316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher /* 311c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * The default use freelist before growing cache policy behaves 312948722f837c4adaf6eefbab648604fc98ce9d036Phillip Lougher * poorly with appending - with many duplicates the caches 313c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * do not grow due to the fact that large queues of outstanding 314c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * fragments/writer blocks do not occur, leading to small caches 315c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * and un-uncessary performance loss to frequent cache 316c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * replacement in the small caches. Therefore with appending 317c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * change the policy to grow the caches before reusing blocks 318c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher * from the freelist 319c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher */ 320c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher cache->first_freelist = first_freelist; 321c97dac5d763d3947b2370b8186611fa655864fccPhillip Lougher 32271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher memset(cache->hash_table, 0, sizeof(struct file_buffer *) * 65536); 32371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_init(&cache->mutex, NULL); 32471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_init(&cache->wait_for_free, NULL); 3258bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cond_init(&cache->wait_for_unlock, NULL); 32671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 32771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher return cache; 32871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 32971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 33071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 33171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougherstruct file_buffer *cache_lookup(struct cache *cache, long long index) 33271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 33371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher /* Lookup block in the cache, if found return with usage count 33471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * incremented, if not found return NULL */ 3359ddeae253410ec344ad8345f722f952749f01419Phillip Lougher int hash = CALCULATE_CACHE_HASH(index); 33671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher struct file_buffer *entry; 33771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 33871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 33971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_lock(&cache->mutex); 34071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 34171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher for(entry = cache->hash_table[hash]; entry; entry = entry->hash_next) 34271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(entry->index == index) 34371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher break; 34471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 34571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(entry) { 34671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher /* found the block in the cache, increment used count and 34771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher * if necessary remove from free list so it won't disappear 34871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher */ 349b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(entry->used == 0) { 350b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher remove_free_list(&cache->free_list, entry); 351b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->used ++; 352b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher } 35371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher entry->used ++; 35471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher } 35571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 35671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_pop(1); 35771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 35871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher return entry; 35971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 36071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 36171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 362b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougherstatic struct file_buffer *cache_freelist(struct cache *cache) 363b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher{ 364b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher struct file_buffer *entry = cache->free_list; 365b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 366b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher remove_free_list(&cache->free_list, entry); 367b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 368b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher /* a block on the free_list is hashed */ 3699ddeae253410ec344ad8345f722f952749f01419Phillip Lougher remove_cache_hash_table(cache, entry); 370b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 371b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->used ++; 372b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher return entry; 373b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher} 374b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 375b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 376b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougherstatic struct file_buffer *cache_alloc(struct cache *cache) 377b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher{ 378b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher struct file_buffer *entry = malloc(sizeof(struct file_buffer) + 379b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->buffer_size); 380b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(entry == NULL) 381b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher MEM_ERROR(); 382b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 383b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher entry->cache = cache; 384b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher entry->free_prev = entry->free_next = NULL; 385b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->count ++; 386b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher return entry; 387b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher} 388b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 389b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher 390316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougherstatic struct file_buffer *_cache_get(struct cache *cache, long long index, 391316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher int hash) 39271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 39371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher /* Get a free block out of the cache indexed on index. */ 394b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher struct file_buffer *entry = NULL; 395ce5862386bf029783b964e778e4478654f107d19Phillip Lougher 39671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 39771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_lock(&cache->mutex); 39871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 39971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher while(1) { 400b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(cache->noshrink_lookup) { 401b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher /* first try to get a block from the free list */ 402b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(cache->first_freelist && cache->free_list) 403b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher entry = cache_freelist(cache); 404b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher else if(cache->count < cache->max_buffers) { 405b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher entry = cache_alloc(cache); 406b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->used ++; 407b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher } else if(!cache->first_freelist && cache->free_list) 408b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher entry = cache_freelist(cache); 409b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher } else { /* shrinking non-lookup cache */ 410b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(cache->count < cache->max_buffers) { 411b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher entry = cache_alloc(cache); 412b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(cache->count > cache->max_count) 413b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->max_count = cache->count; 414b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher } 415b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher } 416316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 417b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(entry) 41871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher break; 419316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 420b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher /* wait for a block */ 421b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher pthread_cond_wait(&cache->wait_for_free, &cache->mutex); 42271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher } 42371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 424316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher /* initialise block and if hash is set insert into the hash table */ 42571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher entry->used = 1; 4268bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->locked = FALSE; 4278bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->wait_on_unlock = FALSE; 42871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher entry->error = FALSE; 429316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher if(hash) { 43071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher entry->index = index; 4319ddeae253410ec344ad8345f722f952749f01419Phillip Lougher insert_cache_hash_table(cache, entry); 43271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher } 43371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 43471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_pop(1); 43571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 43671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher return entry; 43771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 43871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 43971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 440316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougherstruct file_buffer *cache_get(struct cache *cache, long long index) 441316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher{ 442316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher return _cache_get(cache, index, 1); 443316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher} 444316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 445316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 446316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougherstruct file_buffer *cache_get_nohash(struct cache *cache) 447316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher{ 448316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher return _cache_get(cache, 0, 0); 449316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher} 450316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 451316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 45284e20d70e906c24483d0b9dc6a38f310ee78728dPhillip Loughervoid cache_hash(struct file_buffer *entry, long long index) 45371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 45471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher struct cache *cache = entry->cache; 45571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 45671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 45771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_lock(&cache->mutex); 458316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 45984e20d70e906c24483d0b9dc6a38f310ee78728dPhillip Lougher entry->index = index; 46084e20d70e906c24483d0b9dc6a38f310ee78728dPhillip Lougher insert_cache_hash_table(cache, entry); 461316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher 46271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_pop(1); 46371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 46471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 46571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 46671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Loughervoid cache_block_put(struct file_buffer *entry) 46771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher{ 46871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher struct cache *cache; 46971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 470316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher /* 471316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * Finished with this cache entry, once the usage count reaches zero it 472316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * can be reused. 473316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * 474316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * If noshrink_lookup is set, put the block onto the free list. 475316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * As blocks remain accessible via the hash table they can be found 476316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * getting a new lease of life before they are reused. 477316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * 478316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher * if noshrink_lookup is not set then shrink the cache. 479316ab63e3361639621b90a02bbb31d30990dbb63Phillip Lougher */ 48071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 48171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(entry == NULL) 48271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher return; 48371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 48471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher cache = entry->cache; 48571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 48671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 48771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_mutex_lock(&cache->mutex); 48871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 48971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher entry->used --; 49071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher if(entry->used == 0) { 491b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher if(cache->noshrink_lookup) { 49271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher insert_free_list(&cache->free_list, entry); 493b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher cache->used --; 494b4edf5dd9588f281a9d45b893f6be42b282d4ca1Phillip Lougher } else { 49571f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher free(entry); 49671f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher cache->count --; 49771f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher } 49871f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 49971f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher /* One or more threads may be waiting on this block */ 50071f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cond_signal(&cache->wait_for_free); 50171f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher } 50271f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher 50371f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher pthread_cleanup_pop(1); 50471f3964ce67bf6c9eb4816872cd5db1d69d8cf28Phillip Lougher} 505e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher 506e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher 507e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Loughervoid dump_cache(struct cache *cache) 508e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher{ 509e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 510e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher pthread_mutex_lock(&cache->mutex); 511e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher 512c8cd74193087ee5e6cb4f6668970de3bebca35d3Phillip Lougher if(cache->noshrink_lookup) 513fb78d2c217a087e5d53d543f335af0a2ddce5759Phillip Lougher printf("\tMax buffers %d, Current size %d, Used %d, %s\n", 514c8cd74193087ee5e6cb4f6668970de3bebca35d3Phillip Lougher cache->max_buffers, cache->count, cache->used, 515c8cd74193087ee5e6cb4f6668970de3bebca35d3Phillip Lougher cache->free_list ? "Free buffers" : "No free buffers"); 516c8cd74193087ee5e6cb4f6668970de3bebca35d3Phillip Lougher else 517fb78d2c217a087e5d53d543f335af0a2ddce5759Phillip Lougher printf("\tMax buffers %d, Current size %d, Maximum historical " 518c8cd74193087ee5e6cb4f6668970de3bebca35d3Phillip Lougher "size %d\n", cache->max_buffers, cache->count, 519c8cd74193087ee5e6cb4f6668970de3bebca35d3Phillip Lougher cache->max_count); 520e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher 521e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher pthread_cleanup_pop(1); 522e3ef7b81ce21d8da7007daeac4c351d2c2c11f9dPhillip Lougher} 5238bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5248bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5258bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougherstruct file_buffer *cache_get_nowait(struct cache *cache, long long index) 5268bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher{ 5278bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher struct file_buffer *entry = NULL; 5288bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* 5298bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * block doesn't exist, create it, but return it with the 5308bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * locked flag set, so nothing tries to use it while it doesn't 5318bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * contain data. 5328bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * 5338bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * If there's no space in the cache then return NULL. 5348bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher */ 5358bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5368bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 5378bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_mutex_lock(&cache->mutex); 5388bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5398bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* first try to get a block from the free list */ 5408bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher if(cache->first_freelist && cache->free_list) 5418bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry = cache_freelist(cache); 5428bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher else if(cache->count < cache->max_buffers) { 5438bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry = cache_alloc(cache); 5448bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher cache->used ++; 5458bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher } else if(!cache->first_freelist && cache->free_list) 5468bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry = cache_freelist(cache); 5478bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5488bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher if(entry) { 5498bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* initialise block and insert into the hash table */ 5508bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->used = 1; 5518bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->locked = TRUE; 5528bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->wait_on_unlock = FALSE; 5538bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->error = FALSE; 5548bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->index = index; 5558bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher insert_cache_hash_table(cache, entry); 5568bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher } 5578bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5588bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_pop(1); 5598bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5608bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher return entry; 5618bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher} 5628bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5638bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5648bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougherstruct file_buffer *cache_lookup_nowait(struct cache *cache, long long index, 5658bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher char *locked) 5668bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher{ 5678bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* 5688bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * Lookup block in the cache, if found return it with the locked flag 5698bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * indicating whether it is currently locked. In both cases increment 5708bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * the used count. 5718bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * 5728bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * If it doesn't exist in the cache return NULL; 5738bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher */ 5748bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher int hash = CALCULATE_CACHE_HASH(index); 5758bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher struct file_buffer *entry; 5768bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5778bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 5788bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_mutex_lock(&cache->mutex); 5798bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5808bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* first check if the entry already exists */ 5818bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher for(entry = cache->hash_table[hash]; entry; entry = entry->hash_next) 5828bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher if(entry->index == index) 5838bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher break; 5848bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5858bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher if(entry) { 5865dde4966cad49bb8d0060dc3728f64941269d5c5Phillip Lougher if(entry->used == 0) { 5878bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher remove_free_list(&cache->free_list, entry); 5885dde4966cad49bb8d0060dc3728f64941269d5c5Phillip Lougher cache->used ++; 5895dde4966cad49bb8d0060dc3728f64941269d5c5Phillip Lougher } 5908bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->used ++; 5918bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher *locked = entry->locked; 5928bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher } 5938bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5948bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_pop(1); 5958bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5968bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher return entry; 5978bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher} 5988bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 5998bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6008bb17b0275fa35318ad35c8fd477023004f940aaPhillip Loughervoid cache_wait_unlock(struct file_buffer *buffer) 6018bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher{ 6028bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher struct cache *cache = buffer->cache; 6038bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6048bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 6058bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_mutex_lock(&cache->mutex); 6068bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6078bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher while(buffer->locked) { 6088bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* 6098bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * another thread is filling this in, wait until it 6108bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * becomes unlocked. Used has been incremented to ensure it 6118bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * doesn't get reused. By definition a block can't be 6128bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * locked and unused, and so we don't need to worry 6138bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * about it being on the freelist now, but, it may 6148bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * become unused when unlocked unless used is 6158bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * incremented 6168bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher */ 6178bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher buffer->wait_on_unlock = TRUE; 6188bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cond_wait(&cache->wait_for_unlock, &cache->mutex); 6198bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher } 6208bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6218bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_pop(1); 6228bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher} 6238bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6248bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6258bb17b0275fa35318ad35c8fd477023004f940aaPhillip Loughervoid cache_unlock(struct file_buffer *entry) 6268bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher{ 6278bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher struct cache *cache = entry->cache; 6288bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6298bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher /* 6308bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * Unlock this locked cache entry. If anything is waiting for this 6318bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher * to become unlocked, wake it up. 6328bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher */ 6338bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_push((void *) pthread_mutex_unlock, &cache->mutex); 6348bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_mutex_lock(&cache->mutex); 6358bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6368bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->locked = FALSE; 6378bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6388bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher if(entry->wait_on_unlock) { 6398bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher entry->wait_on_unlock = FALSE; 6408bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cond_broadcast(&cache->wait_for_unlock); 6418bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher } 6428bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher 6438bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher pthread_cleanup_pop(1); 6448bb17b0275fa35318ad35c8fd477023004f940aaPhillip Lougher} 645