• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2008 Google Inc. All Rights Reserved.
2 
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 
7 //      http://www.apache.org/licenses/LICENSE-2.0
8 
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 // Thread-safe container of disk blocks
16 
17 // This file must work with autoconf on its public version,
18 // so these includes are correct.
19 #include "disk_blocks.h"
20 
21 #include <utility>
22 
23 // BlockData
BlockData()24 BlockData::BlockData() : address_(0), size_(0),
25                          references_(0), initialized_(false),
26                          pattern_(NULL) {
27   pthread_mutex_init(&data_mutex_, NULL);
28 }
29 
~BlockData()30 BlockData::~BlockData() {
31   pthread_mutex_destroy(&data_mutex_);
32 }
33 
set_initialized()34 void BlockData::set_initialized() {
35   pthread_mutex_lock(&data_mutex_);
36   initialized_ = true;
37   pthread_mutex_unlock(&data_mutex_);
38 }
39 
initialized() const40 bool BlockData::initialized() const {
41   pthread_mutex_lock(&data_mutex_);
42   bool initialized = initialized_;
43   pthread_mutex_unlock(&data_mutex_);
44   return initialized;
45 }
46 
47 // DiskBlockTable
DiskBlockTable()48 DiskBlockTable::DiskBlockTable() : sector_size_(0), write_block_size_(0),
49                                    device_name_(""), device_sectors_(0),
50                                    segment_size_(0), size_(0) {
51   pthread_mutex_init(&data_mutex_, NULL);
52   pthread_mutex_init(&parameter_mutex_, NULL);
53   pthread_cond_init(&data_condition_, NULL);
54 }
55 
~DiskBlockTable()56 DiskBlockTable::~DiskBlockTable() {
57   pthread_mutex_destroy(&data_mutex_);
58   pthread_mutex_destroy(&parameter_mutex_);
59   pthread_cond_destroy(&data_condition_);
60 }
61 
62 // 64-bit non-negative random number generator.  Stolen from
63 // depot/google3/base/tracecontext_unittest.cc.
Random64()64 int64 DiskBlockTable::Random64() {
65   int64 x = random();
66   x = (x << 30) ^ random();
67   x = (x << 30) ^ random();
68   if (x >= 0)
69     return x;
70   else
71     return -x;
72 }
73 
Size()74 uint64 DiskBlockTable::Size() {
75   pthread_mutex_lock(&data_mutex_);
76   uint64 size = size_;
77   pthread_mutex_unlock(&data_mutex_);
78   return size;
79 }
80 
InsertOnStructure(BlockData * block)81 void DiskBlockTable::InsertOnStructure(BlockData *block) {
82   int64 address = block->address();
83   StorageData *sd = new StorageData();
84   sd->block = block;
85   sd->pos = size_;
86   // Creating new block ...
87   pthread_mutex_lock(&data_mutex_);
88   if (pos_to_addr_.size() <= size_) {
89     pos_to_addr_.insert(pos_to_addr_.end(), address);
90   } else {
91     pos_to_addr_[size_] = address;
92   }
93   addr_to_block_[address] = sd;
94   size_++;
95   pthread_cond_broadcast(&data_condition_);
96   pthread_mutex_unlock(&data_mutex_);
97 }
98 
RemoveBlock(BlockData * block)99 int DiskBlockTable::RemoveBlock(BlockData *block) {
100   // For write threads, check the reference counter and remove
101   // it from the structure.
102   int64 address = block->address();
103   AddrToBlockMap::iterator it = addr_to_block_.find(address);
104   int ret = 1;
105   if (it != addr_to_block_.end()) {
106     int curr_pos = it->second->pos;
107     int last_pos = size_ - 1;
108     AddrToBlockMap::iterator last_it = addr_to_block_.find(
109         pos_to_addr_[last_pos]);
110     sat_assert(size_ > 0);
111     sat_assert(last_it != addr_to_block_.end());
112     // Everything is fine, removing block from table.
113     pthread_mutex_lock(&data_mutex_);
114     pos_to_addr_[curr_pos] = pos_to_addr_[last_pos];
115     last_it->second->pos = curr_pos;
116     delete it->second;
117     addr_to_block_.erase(it);
118     size_--;
119     block->DecreaseReferenceCounter();
120     if (block->GetReferenceCounter() == 0)
121       delete block;
122     else if (block->GetReferenceCounter() < 0)
123       ret = 0;
124     pthread_cond_broadcast(&data_condition_);
125     pthread_mutex_unlock(&data_mutex_);
126   } else {
127     ret = 0;
128   }
129   return ret;
130 }
131 
ReleaseBlock(BlockData * block)132 int DiskBlockTable::ReleaseBlock(BlockData *block) {
133   // If caller is a random thread, just check the reference counter.
134   int ret = 1;
135   pthread_mutex_lock(&data_mutex_);
136   int references = block->GetReferenceCounter();
137   if (references == 1)
138     delete block;
139   else if (references > 0)
140     block->DecreaseReferenceCounter();
141   else
142     ret = 0;
143   pthread_mutex_unlock(&data_mutex_);
144   return ret;
145 }
146 
GetRandomBlock()147 BlockData *DiskBlockTable::GetRandomBlock() {
148   struct timespec ts;
149   struct timeval tp;
150   gettimeofday(&tp, NULL);
151   ts.tv_sec  = tp.tv_sec;
152   ts.tv_nsec = tp.tv_usec * 1000;
153   ts.tv_sec += 2;  // Wait for 2 seconds.
154   int result = 0;
155   pthread_mutex_lock(&data_mutex_);
156   while (!size_ && result != ETIMEDOUT) {
157     result = pthread_cond_timedwait(&data_condition_, &data_mutex_, &ts);
158   }
159   if (result == ETIMEDOUT) {
160     pthread_mutex_unlock(&data_mutex_);
161     return NULL;
162   } else {
163     int64 random_number = Random64();
164     int64 random_pos = random_number % size_;
165     int64 address = pos_to_addr_[random_pos];
166     AddrToBlockMap::const_iterator it = addr_to_block_.find(address);
167     sat_assert(it != addr_to_block_.end());
168     BlockData *b = it->second->block;
169     // A block is returned only if its content is written on disk.
170     if (b->initialized()) {
171       b->IncreaseReferenceCounter();
172     } else {
173       b = NULL;
174     }
175     pthread_mutex_unlock(&data_mutex_);
176     return b;
177   }
178 }
179 
SetParameters(int sector_size,int write_block_size,int64 device_sectors,int64 segment_size,const string & device_name)180 void DiskBlockTable::SetParameters(int sector_size,
181                                    int write_block_size,
182                                    int64 device_sectors,
183                                    int64 segment_size,
184                                    const string& device_name) {
185   sat_assert(size_ == 0);
186   pthread_mutex_lock(&parameter_mutex_);
187   sector_size_ = sector_size;
188   write_block_size_ = write_block_size;
189   device_sectors_ = device_sectors;
190   segment_size_ = segment_size;
191   device_name_ = device_name;
192   pthread_mutex_unlock(&parameter_mutex_);
193 }
194 
GetUnusedBlock(int64 segment)195 BlockData *DiskBlockTable::GetUnusedBlock(int64 segment) {
196   int64 sector = 0;
197   BlockData *block = new BlockData();
198   bool good_sequence = false;
199   if (block == NULL) {
200     logprintf(0, "Process Error: Unable to allocate memory "
201               "for sector data for disk %s.\n", device_name_.c_str());
202     return NULL;
203   }
204   pthread_mutex_lock(&parameter_mutex_);
205   sat_assert(device_sectors_ != 0);
206   // Align the first sector with the beginning of a write block
207   int num_sectors = write_block_size_ / sector_size_;
208   for (int i = 0; i < kBlockRetry && !good_sequence; i++) {
209     good_sequence = true;
210     // Use the entire disk or a small segment of the disk to allocate the first
211     // sector in the block from.
212     if (segment_size_ == -1) {
213       sector = (Random64() & 0x7FFFFFFFFFFFFFFFLL) % (
214           device_sectors_ / num_sectors);
215       sector *= num_sectors;
216     } else {
217       sector = (Random64() & 0x7FFFFFFFFFFFFFFFLL) % (
218           segment_size_ / num_sectors);
219       sector *= num_sectors;
220       sector += segment * segment_size_;
221       // Make sure the block is within the segment.
222       if (sector + num_sectors > (segment + 1) * segment_size_) {
223         good_sequence = false;
224         continue;
225       }
226     }
227     // Make sure the entire block is in range.
228     if (sector + num_sectors > device_sectors_) {
229       good_sequence = false;
230       continue;
231     }
232     // Check to see if the block is free. Since the blocks are
233     // now aligned to the write_block_size, it is not necessary
234     // to check each sector, just the first block (a sector
235     // overlap will never occur).
236     pthread_mutex_lock(&data_mutex_);
237     if (addr_to_block_.find(sector) != addr_to_block_.end()) {
238       good_sequence = false;
239     }
240     pthread_mutex_unlock(&data_mutex_);
241   }
242 
243   if (good_sequence) {
244     block->set_address(sector);
245     block->set_size(write_block_size_);
246     block->IncreaseReferenceCounter();
247     InsertOnStructure(block);
248   } else {
249     // No contiguous sequence of num_sectors sectors was found within
250     // kBlockRetry iterations so return an error value.
251     delete block;
252     block = NULL;
253   }
254   pthread_mutex_unlock(&parameter_mutex_);
255   return block;
256 }
257