15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "net/disk_cache/blockfile/sparse_control.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/bind.h" 8eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/format_macros.h" 990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "base/logging.h" 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/message_loop/message_loop.h" 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/strings/string_util.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/strings/stringprintf.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/time/time.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/base/io_buffer.h" 15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "net/base/net_errors.h" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/disk_cache/blockfile/backend_impl.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/disk_cache/blockfile/entry_impl.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/disk_cache/blockfile/file.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/disk_cache/net_log_parameters.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using base::Time; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Stream of the sparse data index. 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kSparseIndex = 2; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Stream of the sparse data. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kSparseData = 1; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We can have up to 64k children. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kMaxMapSize = 8 * 1024; 33eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 34eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// The maximum number of bytes that a child can store. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kMaxEntrySize = 0x100000; 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The size of each data block (tracked by the child allocation bitmap). 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kBlockSize = 1024; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 40eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// Returns the name of a child entry given the base_name and signature of the 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// parent and the child_id. 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If the entry is called entry_name, child entries will be named something 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// like Range_entry_name:XXX:YYY where XXX is the entry signature and YYY is the 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// number of the particular child. 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)std::string GenerateChildName(const std::string& base_name, int64 signature, 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 child_id) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return base::StringPrintf("Range_%s:%" PRIx64 ":%" PRIx64, base_name.c_str(), 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signature, child_id); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class deletes the children of a sparse entry. 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class ChildrenDeleter 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : public base::RefCounted<ChildrenDeleter>, 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public disk_cache::FileIOCallback { 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) public: 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ChildrenDeleter(disk_cache::BackendImpl* backend, const std::string& name) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : backend_(backend->GetWeakPtr()), name_(name), signature_(0) {} 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void OnFileIOComplete(int bytes_copied) OVERRIDE; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Two ways of deleting the children: if we have the children map, use Start() 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // directly, otherwise pass the data address to ReadData(). 63eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch void Start(char* buffer, int len); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ReadData(disk_cache::Addr address, int len); 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 67eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch friend class base::RefCounted<ChildrenDeleter>; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~ChildrenDeleter() {} 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void DeleteChildren(); 71eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 72eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch base::WeakPtr<disk_cache::BackendImpl> backend_; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string name_; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) disk_cache::Bitmap children_map_; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 signature_; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_ptr<char[]> buffer_; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(ChildrenDeleter); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is the callback of the file operation. 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ChildrenDeleter::OnFileIOComplete(int bytes_copied) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* buffer = buffer_.release(); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Start(buffer, bytes_copied); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ChildrenDeleter::Start(char* buffer, int len) { 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_.reset(buffer); 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (len < static_cast<int>(sizeof(disk_cache::SparseData))) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Release(); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Just copy the information from |buffer|, delete |buffer| and start deleting 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the child entries. 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) disk_cache::SparseData* data = 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reinterpret_cast<disk_cache::SparseData*>(buffer); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) signature_ = data->header.signature; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_bits = (len - sizeof(disk_cache::SparseHeader)) * 8; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) children_map_.Resize(num_bits, false); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) children_map_.SetMap(data->bitmap, num_bits / 32); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_.reset(); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeleteChildren(); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ChildrenDeleter::ReadData(disk_cache::Addr address, int len) { 106eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch DCHECK(address.is_block_file()); 107eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch if (!backend_) 108eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return Release(); 109eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 110eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch disk_cache::File* file(backend_->File(address)); 111eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch if (!file) 112eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return Release(); 113eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 114eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch size_t file_offset = address.start_block() * address.BlockSize() + 115eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch disk_cache::kBlockHeaderSize; 116eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 117eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch buffer_.reset(new char[len]); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool completed; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!file->Read(buffer_.get(), len, file_offset, this, &completed)) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Release(); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (completed) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OnFileIOComplete(len); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // And wait until OnFileIOComplete gets called. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ChildrenDeleter::DeleteChildren() { 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int child_id = 0; 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!children_map_.FindNextSetBit(&child_id) || !backend_) { 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We are done. Just delete this object. 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Release(); 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::string child_name = GenerateChildName(name_, signature_, child_id); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) backend_->SyncDoomEntry(child_name); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) children_map_.Set(child_id, false); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Post a task to delete the next child. 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::MessageLoop::current()->PostTask( 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FROM_HERE, base::Bind(&ChildrenDeleter::DeleteChildren, this)); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 142eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ----------------------------------------------------------------------- 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the NetLog event type corresponding to a SparseOperation. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)net::NetLog::EventType GetSparseEventType( 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) disk_cache::SparseControl::SparseOperation operation) { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (operation) { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case disk_cache::SparseControl::kReadOperation: 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return net::NetLog::TYPE_SPARSE_READ; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case disk_cache::SparseControl::kWriteOperation: 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return net::NetLog::TYPE_SPARSE_WRITE; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case disk_cache::SparseControl::kGetRangeOperation: 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return net::NetLog::TYPE_SPARSE_GET_RANGE; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NOTREACHED(); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return net::NetLog::TYPE_CANCELLED; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Logs the end event for |operation| on a child entry. Range operations log 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// no events for each child they search through. 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void LogChildOperationEnd(const net::BoundNetLog& net_log, 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) disk_cache::SparseControl::SparseOperation operation, 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int result) { 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (net_log.IsLogging()) { 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) net::NetLog::EventType event_type; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (operation) { 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case disk_cache::SparseControl::kReadOperation: 170 event_type = net::NetLog::TYPE_SPARSE_READ_CHILD_DATA; 171 break; 172 case disk_cache::SparseControl::kWriteOperation: 173 event_type = net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA; 174 break; 175 case disk_cache::SparseControl::kGetRangeOperation: 176 return; 177 default: 178 NOTREACHED(); 179 return; 180 } 181 net_log.EndEventWithNetErrorCode(event_type, result); 182 } 183} 184 185} // namespace. 186 187namespace disk_cache { 188 189SparseControl::SparseControl(EntryImpl* entry) 190 : entry_(entry), 191 child_(NULL), 192 operation_(kNoOperation), 193 pending_(false), 194 finished_(false), 195 init_(false), 196 range_found_(false), 197 abort_(false), 198 child_map_(child_data_.bitmap, kNumSparseBits, kNumSparseBits / 32), 199 offset_(0), 200 buf_len_(0), 201 child_offset_(0), 202 child_len_(0), 203 result_(0) { 204 memset(&sparse_header_, 0, sizeof(sparse_header_)); 205 memset(&child_data_, 0, sizeof(child_data_)); 206} 207 208SparseControl::~SparseControl() { 209 if (child_) 210 CloseChild(); 211 if (init_) 212 WriteSparseData(); 213} 214 215bool SparseControl::CouldBeSparse() const { 216 DCHECK(!init_); 217 218 if (entry_->GetDataSize(kSparseData)) 219 return false; 220 221 // We don't verify the data, just see if it could be there. 222 return (entry_->GetDataSize(kSparseIndex) != 0); 223} 224 225int SparseControl::StartIO(SparseOperation op, int64 offset, net::IOBuffer* buf, 226 int buf_len, const CompletionCallback& callback) { 227 DCHECK(init_); 228 // We don't support simultaneous IO for sparse data. 229 if (operation_ != kNoOperation) 230 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 231 232 if (offset < 0 || buf_len < 0) 233 return net::ERR_INVALID_ARGUMENT; 234 235 // We only support up to 64 GB. 236 if (offset + buf_len >= 0x1000000000LL || offset + buf_len < 0) 237 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 238 239 DCHECK(!user_buf_); 240 DCHECK(user_callback_.is_null()); 241 242 if (!buf && (op == kReadOperation || op == kWriteOperation)) 243 return 0; 244 245 // Copy the operation parameters. 246 operation_ = op; 247 offset_ = offset; 248 user_buf_ = buf ? new net::DrainableIOBuffer(buf, buf_len) : NULL; 249 buf_len_ = buf_len; 250 user_callback_ = callback; 251 252 result_ = 0; 253 pending_ = false; 254 finished_ = false; 255 abort_ = false; 256 257 if (entry_->net_log().IsLogging()) { 258 entry_->net_log().BeginEvent( 259 GetSparseEventType(operation_), 260 CreateNetLogSparseOperationCallback(offset_, buf_len_)); 261 } 262 DoChildrenIO(); 263 264 if (!pending_) { 265 // Everything was done synchronously. 266 operation_ = kNoOperation; 267 user_buf_ = NULL; 268 user_callback_.Reset(); 269 return result_; 270 } 271 272 return net::ERR_IO_PENDING; 273} 274 275int SparseControl::GetAvailableRange(int64 offset, int len, int64* start) { 276 DCHECK(init_); 277 // We don't support simultaneous IO for sparse data. 278 if (operation_ != kNoOperation) 279 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 280 281 DCHECK(start); 282 283 range_found_ = false; 284 int result = StartIO( 285 kGetRangeOperation, offset, NULL, len, CompletionCallback()); 286 if (range_found_) { 287 *start = offset_; 288 return result; 289 } 290 291 // This is a failure. We want to return a valid start value in any case. 292 *start = offset; 293 return result < 0 ? result : 0; // Don't mask error codes to the caller. 294} 295 296void SparseControl::CancelIO() { 297 if (operation_ == kNoOperation) 298 return; 299 abort_ = true; 300} 301 302int SparseControl::ReadyToUse(const CompletionCallback& callback) { 303 if (!abort_) 304 return net::OK; 305 306 // We'll grab another reference to keep this object alive because we just have 307 // one extra reference due to the pending IO operation itself, but we'll 308 // release that one before invoking user_callback_. 309 entry_->AddRef(); // Balanced in DoAbortCallbacks. 310 abort_callbacks_.push_back(callback); 311 return net::ERR_IO_PENDING; 312} 313 314// Static 315void SparseControl::DeleteChildren(EntryImpl* entry) { 316 DCHECK(entry->GetEntryFlags() & PARENT_ENTRY); 317 int data_len = entry->GetDataSize(kSparseIndex); 318 if (data_len < static_cast<int>(sizeof(SparseData)) || 319 entry->GetDataSize(kSparseData)) 320 return; 321 322 int map_len = data_len - sizeof(SparseHeader); 323 if (map_len > kMaxMapSize || map_len % 4) 324 return; 325 326 char* buffer; 327 Addr address; 328 entry->GetData(kSparseIndex, &buffer, &address); 329 if (!buffer && !address.is_initialized()) 330 return; 331 332 entry->net_log().AddEvent(net::NetLog::TYPE_SPARSE_DELETE_CHILDREN); 333 334 DCHECK(entry->backend_); 335 ChildrenDeleter* deleter = new ChildrenDeleter(entry->backend_.get(), 336 entry->GetKey()); 337 // The object will self destruct when finished. 338 deleter->AddRef(); 339 340 if (buffer) { 341 base::MessageLoop::current()->PostTask( 342 FROM_HERE, 343 base::Bind(&ChildrenDeleter::Start, deleter, buffer, data_len)); 344 } else { 345 base::MessageLoop::current()->PostTask( 346 FROM_HERE, 347 base::Bind(&ChildrenDeleter::ReadData, deleter, address, data_len)); 348 } 349} 350 351// ----------------------------------------------------------------------- 352 353int SparseControl::Init() { 354 DCHECK(!init_); 355 356 // We should not have sparse data for the exposed entry. 357 if (entry_->GetDataSize(kSparseData)) 358 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 359 360 // Now see if there is something where we store our data. 361 int rv = net::OK; 362 int data_len = entry_->GetDataSize(kSparseIndex); 363 if (!data_len) { 364 rv = CreateSparseEntry(); 365 } else { 366 rv = OpenSparseEntry(data_len); 367 } 368 369 if (rv == net::OK) 370 init_ = true; 371 return rv; 372} 373 374// We are going to start using this entry to store sparse data, so we have to 375// initialize our control info. 376int SparseControl::CreateSparseEntry() { 377 if (CHILD_ENTRY & entry_->GetEntryFlags()) 378 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 379 380 memset(&sparse_header_, 0, sizeof(sparse_header_)); 381 sparse_header_.signature = Time::Now().ToInternalValue(); 382 sparse_header_.magic = kIndexMagic; 383 sparse_header_.parent_key_len = entry_->GetKey().size(); 384 children_map_.Resize(kNumSparseBits, true); 385 386 // Save the header. The bitmap is saved in the destructor. 387 scoped_refptr<net::IOBuffer> buf( 388 new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_))); 389 390 int rv = entry_->WriteData(kSparseIndex, 0, buf.get(), sizeof(sparse_header_), 391 CompletionCallback(), false); 392 if (rv != sizeof(sparse_header_)) { 393 DLOG(ERROR) << "Unable to save sparse_header_"; 394 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 395 } 396 397 entry_->SetEntryFlags(PARENT_ENTRY); 398 return net::OK; 399} 400 401// We are opening an entry from disk. Make sure that our control data is there. 402int SparseControl::OpenSparseEntry(int data_len) { 403 if (data_len < static_cast<int>(sizeof(SparseData))) 404 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 405 406 if (entry_->GetDataSize(kSparseData)) 407 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 408 409 if (!(PARENT_ENTRY & entry_->GetEntryFlags())) 410 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 411 412 // Dont't go over board with the bitmap. 8 KB gives us offsets up to 64 GB. 413 int map_len = data_len - sizeof(sparse_header_); 414 if (map_len > kMaxMapSize || map_len % 4) 415 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 416 417 scoped_refptr<net::IOBuffer> buf( 418 new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_))); 419 420 // Read header. 421 int rv = entry_->ReadData(kSparseIndex, 0, buf.get(), sizeof(sparse_header_), 422 CompletionCallback()); 423 if (rv != static_cast<int>(sizeof(sparse_header_))) 424 return net::ERR_CACHE_READ_FAILURE; 425 426 // The real validation should be performed by the caller. This is just to 427 // double check. 428 if (sparse_header_.magic != kIndexMagic || 429 sparse_header_.parent_key_len != 430 static_cast<int>(entry_->GetKey().size())) 431 return net::ERR_CACHE_OPERATION_NOT_SUPPORTED; 432 433 // Read the actual bitmap. 434 buf = new net::IOBuffer(map_len); 435 rv = entry_->ReadData(kSparseIndex, sizeof(sparse_header_), buf.get(), 436 map_len, CompletionCallback()); 437 if (rv != map_len) 438 return net::ERR_CACHE_READ_FAILURE; 439 440 // Grow the bitmap to the current size and copy the bits. 441 children_map_.Resize(map_len * 8, false); 442 children_map_.SetMap(reinterpret_cast<uint32*>(buf->data()), map_len); 443 return net::OK; 444} 445 446bool SparseControl::OpenChild() { 447 DCHECK_GE(result_, 0); 448 449 std::string key = GenerateChildKey(); 450 if (child_) { 451 // Keep using the same child or open another one?. 452 if (key == child_->GetKey()) 453 return true; 454 CloseChild(); 455 } 456 457 // See if we are tracking this child. 458 if (!ChildPresent()) 459 return ContinueWithoutChild(key); 460 461 if (!entry_->backend_) 462 return false; 463 464 child_ = entry_->backend_->OpenEntryImpl(key); 465 if (!child_) 466 return ContinueWithoutChild(key); 467 468 EntryImpl* child = static_cast<EntryImpl*>(child_); 469 if (!(CHILD_ENTRY & child->GetEntryFlags()) || 470 child->GetDataSize(kSparseIndex) < 471 static_cast<int>(sizeof(child_data_))) 472 return KillChildAndContinue(key, false); 473 474 scoped_refptr<net::WrappedIOBuffer> buf( 475 new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_))); 476 477 // Read signature. 478 int rv = child_->ReadData(kSparseIndex, 0, buf.get(), sizeof(child_data_), 479 CompletionCallback()); 480 if (rv != sizeof(child_data_)) 481 return KillChildAndContinue(key, true); // This is a fatal failure. 482 483 if (child_data_.header.signature != sparse_header_.signature || 484 child_data_.header.magic != kIndexMagic) 485 return KillChildAndContinue(key, false); 486 487 if (child_data_.header.last_block_len < 0 || 488 child_data_.header.last_block_len > kBlockSize) { 489 // Make sure these values are always within range. 490 child_data_.header.last_block_len = 0; 491 child_data_.header.last_block = -1; 492 } 493 494 return true; 495} 496 497void SparseControl::CloseChild() { 498 scoped_refptr<net::WrappedIOBuffer> buf( 499 new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_))); 500 501 // Save the allocation bitmap before closing the child entry. 502 int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_), 503 CompletionCallback(), 504 false); 505 if (rv != sizeof(child_data_)) 506 DLOG(ERROR) << "Failed to save child data"; 507 child_->Release(); 508 child_ = NULL; 509} 510 511// We were not able to open this child; see what we can do. 512bool SparseControl::ContinueWithoutChild(const std::string& key) { 513 if (kReadOperation == operation_) 514 return false; 515 if (kGetRangeOperation == operation_) 516 return true; 517 518 if (!entry_->backend_) 519 return false; 520 521 child_ = entry_->backend_->CreateEntryImpl(key); 522 if (!child_) { 523 child_ = NULL; 524 result_ = net::ERR_CACHE_READ_FAILURE; 525 return false; 526 } 527 // Write signature. 528 InitChildData(); 529 return true; 530} 531 532void SparseControl::WriteSparseData() { 533 scoped_refptr<net::IOBuffer> buf(new net::WrappedIOBuffer( 534 reinterpret_cast<const char*>(children_map_.GetMap()))); 535 536 int len = children_map_.ArraySize() * 4; 537 int rv = entry_->WriteData(kSparseIndex, sizeof(sparse_header_), buf.get(), 538 len, CompletionCallback(), false); 539 if (rv != len) { 540 DLOG(ERROR) << "Unable to save sparse map"; 541 } 542} 543 544bool SparseControl::DoChildIO() { 545 finished_ = true; 546 if (!buf_len_ || result_ < 0) 547 return false; 548 549 if (!OpenChild()) 550 return false; 551 552 if (!VerifyRange()) 553 return false; 554 555 // We have more work to do. Let's not trigger a callback to the caller. 556 finished_ = false; 557 CompletionCallback callback; 558 if (!user_callback_.is_null()) { 559 callback = 560 base::Bind(&SparseControl::OnChildIOCompleted, base::Unretained(this)); 561 } 562 563 int rv = 0; 564 switch (operation_) { 565 case kReadOperation: 566 if (entry_->net_log().IsLogging()) { 567 entry_->net_log().BeginEvent( 568 net::NetLog::TYPE_SPARSE_READ_CHILD_DATA, 569 CreateNetLogSparseReadWriteCallback(child_->net_log().source(), 570 child_len_)); 571 } 572 rv = child_->ReadDataImpl(kSparseData, child_offset_, user_buf_.get(), 573 child_len_, callback); 574 break; 575 case kWriteOperation: 576 if (entry_->net_log().IsLogging()) { 577 entry_->net_log().BeginEvent( 578 net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA, 579 CreateNetLogSparseReadWriteCallback(child_->net_log().source(), 580 child_len_)); 581 } 582 rv = child_->WriteDataImpl(kSparseData, child_offset_, user_buf_.get(), 583 child_len_, callback, false); 584 break; 585 case kGetRangeOperation: 586 rv = DoGetAvailableRange(); 587 break; 588 default: 589 NOTREACHED(); 590 } 591 592 if (rv == net::ERR_IO_PENDING) { 593 if (!pending_) { 594 pending_ = true; 595 // The child will protect himself against closing the entry while IO is in 596 // progress. However, this entry can still be closed, and that would not 597 // be a good thing for us, so we increase the refcount until we're 598 // finished doing sparse stuff. 599 entry_->AddRef(); // Balanced in DoUserCallback. 600 } 601 return false; 602 } 603 if (!rv) 604 return false; 605 606 DoChildIOCompleted(rv); 607 return true; 608} 609 610void SparseControl::DoChildIOCompleted(int result) { 611 LogChildOperationEnd(entry_->net_log(), operation_, result); 612 if (result < 0) { 613 // We fail the whole operation if we encounter an error. 614 result_ = result; 615 return; 616 } 617 618 UpdateRange(result); 619 620 result_ += result; 621 offset_ += result; 622 buf_len_ -= result; 623 624 // We'll be reusing the user provided buffer for the next chunk. 625 if (buf_len_ && user_buf_) 626 user_buf_->DidConsume(result); 627} 628 629std::string SparseControl::GenerateChildKey() { 630 return GenerateChildName(entry_->GetKey(), sparse_header_.signature, 631 offset_ >> 20); 632} 633 634// We are deleting the child because something went wrong. 635bool SparseControl::KillChildAndContinue(const std::string& key, bool fatal) { 636 SetChildBit(false); 637 child_->DoomImpl(); 638 child_->Release(); 639 child_ = NULL; 640 if (fatal) { 641 result_ = net::ERR_CACHE_READ_FAILURE; 642 return false; 643 } 644 return ContinueWithoutChild(key); 645} 646 647bool SparseControl::ChildPresent() { 648 int child_bit = static_cast<int>(offset_ >> 20); 649 if (children_map_.Size() <= child_bit) 650 return false; 651 652 return children_map_.Get(child_bit); 653} 654 655void SparseControl::SetChildBit(bool value) { 656 int child_bit = static_cast<int>(offset_ >> 20); 657 658 // We may have to increase the bitmap of child entries. 659 if (children_map_.Size() <= child_bit) 660 children_map_.Resize(Bitmap::RequiredArraySize(child_bit + 1) * 32, true); 661 662 children_map_.Set(child_bit, value); 663} 664 665bool SparseControl::VerifyRange() { 666 DCHECK_GE(result_, 0); 667 668 child_offset_ = static_cast<int>(offset_) & (kMaxEntrySize - 1); 669 child_len_ = std::min(buf_len_, kMaxEntrySize - child_offset_); 670 671 // We can write to (or get info from) anywhere in this child. 672 if (operation_ != kReadOperation) 673 return true; 674 675 // Check that there are no holes in this range. 676 int last_bit = (child_offset_ + child_len_ + 1023) >> 10; 677 int start = child_offset_ >> 10; 678 if (child_map_.FindNextBit(&start, last_bit, false)) { 679 // Something is not here. 680 DCHECK_GE(child_data_.header.last_block_len, 0); 681 DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize); 682 int partial_block_len = PartialBlockLength(start); 683 if (start == child_offset_ >> 10) { 684 // It looks like we don't have anything. 685 if (partial_block_len <= (child_offset_ & (kBlockSize - 1))) 686 return false; 687 } 688 689 // We have the first part. 690 child_len_ = (start << 10) - child_offset_; 691 if (partial_block_len) { 692 // We may have a few extra bytes. 693 child_len_ = std::min(child_len_ + partial_block_len, buf_len_); 694 } 695 // There is no need to read more after this one. 696 buf_len_ = child_len_; 697 } 698 return true; 699} 700 701void SparseControl::UpdateRange(int result) { 702 if (result <= 0 || operation_ != kWriteOperation) 703 return; 704 705 DCHECK_GE(child_data_.header.last_block_len, 0); 706 DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize); 707 708 // Write the bitmap. 709 int first_bit = child_offset_ >> 10; 710 int block_offset = child_offset_ & (kBlockSize - 1); 711 if (block_offset && (child_data_.header.last_block != first_bit || 712 child_data_.header.last_block_len < block_offset)) { 713 // The first block is not completely filled; ignore it. 714 first_bit++; 715 } 716 717 int last_bit = (child_offset_ + result) >> 10; 718 block_offset = (child_offset_ + result) & (kBlockSize - 1); 719 720 // This condition will hit with the following criteria: 721 // 1. The first byte doesn't follow the last write. 722 // 2. The first byte is in the middle of a block. 723 // 3. The first byte and the last byte are in the same block. 724 if (first_bit > last_bit) 725 return; 726 727 if (block_offset && !child_map_.Get(last_bit)) { 728 // The last block is not completely filled; save it for later. 729 child_data_.header.last_block = last_bit; 730 child_data_.header.last_block_len = block_offset; 731 } else { 732 child_data_.header.last_block = -1; 733 } 734 735 child_map_.SetRange(first_bit, last_bit, true); 736} 737 738int SparseControl::PartialBlockLength(int block_index) const { 739 if (block_index == child_data_.header.last_block) 740 return child_data_.header.last_block_len; 741 742 // This may be the last stored index. 743 int entry_len = child_->GetDataSize(kSparseData); 744 if (block_index == entry_len >> 10) 745 return entry_len & (kBlockSize - 1); 746 747 // This is really empty. 748 return 0; 749} 750 751void SparseControl::InitChildData() { 752 // We know the real type of child_. 753 EntryImpl* child = static_cast<EntryImpl*>(child_); 754 child->SetEntryFlags(CHILD_ENTRY); 755 756 memset(&child_data_, 0, sizeof(child_data_)); 757 child_data_.header = sparse_header_; 758 759 scoped_refptr<net::WrappedIOBuffer> buf( 760 new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_))); 761 762 int rv = child_->WriteData(kSparseIndex, 0, buf.get(), sizeof(child_data_), 763 CompletionCallback(), false); 764 if (rv != sizeof(child_data_)) 765 DLOG(ERROR) << "Failed to save child data"; 766 SetChildBit(true); 767} 768 769int SparseControl::DoGetAvailableRange() { 770 if (!child_) 771 return child_len_; // Move on to the next child. 772 773 // Check that there are no holes in this range. 774 int last_bit = (child_offset_ + child_len_ + 1023) >> 10; 775 int start = child_offset_ >> 10; 776 int partial_start_bytes = PartialBlockLength(start); 777 int found = start; 778 int bits_found = child_map_.FindBits(&found, last_bit, true); 779 780 // We don't care if there is a partial block in the middle of the range. 781 int block_offset = child_offset_ & (kBlockSize - 1); 782 if (!bits_found && partial_start_bytes <= block_offset) 783 return child_len_; 784 785 // We are done. Just break the loop and reset result_ to our real result. 786 range_found_ = true; 787 788 // found now points to the first 1. Lets see if we have zeros before it. 789 int empty_start = std::max((found << 10) - child_offset_, 0); 790 791 int bytes_found = bits_found << 10; 792 bytes_found += PartialBlockLength(found + bits_found); 793 794 if (start == found) 795 bytes_found -= block_offset; 796 797 // If the user is searching past the end of this child, bits_found is the 798 // right result; otherwise, we have some empty space at the start of this 799 // query that we have to subtract from the range that we searched. 800 result_ = std::min(bytes_found, child_len_ - empty_start); 801 802 if (!bits_found) { 803 result_ = std::min(partial_start_bytes - block_offset, child_len_); 804 empty_start = 0; 805 } 806 807 // Only update offset_ when this query found zeros at the start. 808 if (empty_start) 809 offset_ += empty_start; 810 811 // This will actually break the loop. 812 buf_len_ = 0; 813 return 0; 814} 815 816void SparseControl::DoUserCallback() { 817 DCHECK(!user_callback_.is_null()); 818 CompletionCallback cb = user_callback_; 819 user_callback_.Reset(); 820 user_buf_ = NULL; 821 pending_ = false; 822 operation_ = kNoOperation; 823 int rv = result_; 824 entry_->Release(); // Don't touch object after this line. 825 cb.Run(rv); 826} 827 828void SparseControl::DoAbortCallbacks() { 829 for (size_t i = 0; i < abort_callbacks_.size(); i++) { 830 // Releasing all references to entry_ may result in the destruction of this 831 // object so we should not be touching it after the last Release(). 832 CompletionCallback cb = abort_callbacks_[i]; 833 if (i == abort_callbacks_.size() - 1) 834 abort_callbacks_.clear(); 835 836 entry_->Release(); // Don't touch object after this line. 837 cb.Run(net::OK); 838 } 839} 840 841void SparseControl::OnChildIOCompleted(int result) { 842 DCHECK_NE(net::ERR_IO_PENDING, result); 843 DoChildIOCompleted(result); 844 845 if (abort_) { 846 // We'll return the current result of the operation, which may be less than 847 // the bytes to read or write, but the user cancelled the operation. 848 abort_ = false; 849 if (entry_->net_log().IsLogging()) { 850 entry_->net_log().AddEvent(net::NetLog::TYPE_CANCELLED); 851 entry_->net_log().EndEvent(GetSparseEventType(operation_)); 852 } 853 // We have an indirect reference to this object for every callback so if 854 // there is only one callback, we may delete this object before reaching 855 // DoAbortCallbacks. 856 bool has_abort_callbacks = !abort_callbacks_.empty(); 857 DoUserCallback(); 858 if (has_abort_callbacks) 859 DoAbortCallbacks(); 860 return; 861 } 862 863 // We are running a callback from the message loop. It's time to restart what 864 // we were doing before. 865 DoChildrenIO(); 866} 867 868} // namespace disk_cache 869