src/pagespeed/kernel/sharedmem/shared_mem_cache_data.cc - incubator-pagespeed-debian - Git at Google

 /*
  * Copyright 2011 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 // Author: morlovich@google.com (Maksim Orlovich)

 // Data structure operation helpers for SharedMemCache. See the top of
 // shared_mem_cache.cc for data format descriptions.

 #include "pagespeed/kernel/sharedmem/shared_mem_cache_data.h"

 #include "base/logging.h"
 #include "pagespeed/kernel/base/abstract_mutex.h"
 #include "pagespeed/kernel/base/abstract_shared_mem.h"
 #include "pagespeed/kernel/base/message_handler.h"
 #include "pagespeed/kernel/base/string_util.h"

 namespace net_instaweb {

 namespace SharedMemCacheData {

 namespace {
 // Assumes align is power-of-2
 inline size_t AlignTo(size_t alignment, size_t in) {
   return (in + (alignment - 1)) & ~(alignment - 1);
 }

 double percent(int64 portion, int64 total) {
   return static_cast<double>(portion) / static_cast<double>(total) * 100.0;
 }

 }  // namespace

 template<size_t kBlockSize>
 struct Sector<kBlockSize>::MemLayout {
   MemLayout(size_t mutex_size, size_t cache_entries, size_t data_blocks) {
     // Check out alignment assumptions -- everything must be of a size
     // that's multiple of 8. The exact sizes don't matter too much, but
     // we check it anyway to avoid surprises.
     CHECK_EQ(96u, sizeof(SectorHeader));
     CHECK_EQ(48u, sizeof(CacheEntry));

     header_bytes = AlignTo(8, sizeof(SectorHeader) + mutex_size);
     block_successor_list_bytes =
         AlignTo(8, sizeof(BlockNum) * data_blocks);
     size_t directory_size = sizeof(CacheEntry) * cache_entries;
     metadata_bytes =
         AlignTo(kBlockSize,
                 header_bytes + directory_size + block_successor_list_bytes);
   }

   size_t header_bytes;  // also offset to the block successor list.
   size_t block_successor_list_bytes;
   size_t metadata_bytes;  // e.g. offset to the blocks.
 };

 template<size_t kBlockSize>
 Sector<kBlockSize>::Sector(AbstractSharedMemSegment* segment,
                            size_t sector_offset, size_t cache_entries,
                            size_t data_blocks)
     : cache_entries_(cache_entries),
       data_blocks_(data_blocks),
       segment_(segment),
       sector_offset_(sector_offset) {
   MemLayout layout(segment->SharedMutexSize(), cache_entries, data_blocks);
   char* base = const_cast<char*>(segment->Base()) + sector_offset;
   sector_header_ = reinterpret_cast<SectorHeader*>(base);
   block_successors_ = reinterpret_cast<BlockNum*>(base + layout.header_bytes);
   directory_base_ =
       base + layout.header_bytes + layout.block_successor_list_bytes;
   blocks_base_ = base + layout.metadata_bytes;
 }

 template<size_t kBlockSize>
 Sector<kBlockSize>::~Sector() {
 }

 template<size_t kBlockSize>
 bool Sector<kBlockSize>::Attach(MessageHandler* handler) {
   mutex_.reset(
       segment_->AttachToSharedMutex(sector_offset_ + sizeof(SectorHeader)));
   return (mutex_.get() != NULL);
 }

 template<size_t kBlockSize>
 bool Sector<kBlockSize>::Initialize(MessageHandler* handler)
     NO_THREAD_SAFETY_ANALYSIS {
   if (!segment_->InitializeSharedMutex(sector_offset_ + sizeof(SectorHeader),
                                        handler)) {
     return false;
   }

   // Connect to the mutex, now it's created.
   if (!Attach(handler)) {
     return false;
   }

   // Initialize the LRU and the cache entry.
   sector_header_->lru_list_front = kInvalidEntry;
   sector_header_->lru_list_rear = kInvalidEntry;
   for (size_t c = 0; c < cache_entries_; ++c) {
     CacheEntry* entry = EntryAt(c);
     entry->lru_prev = kInvalidEntry;
     entry->lru_next = kInvalidEntry;
     entry->first_block = kInvalidBlock;
   }

   // Initialize the freelist and block successor list.
   sector_header_->free_list_front = kInvalidBlock;
   BlockVector all_blocks;
   for (size_t c = 0; c < data_blocks_; ++c) {
     all_blocks.push_back(static_cast<BlockNum>(c));
   }
   ReturnBlocksToFreeList(all_blocks);
   sector_header_->stats.used_blocks = 0;

   return true;
 }

 template<size_t kBlockSize>
 size_t Sector<kBlockSize>::RequiredSize(AbstractSharedMem* shmem_runtime,
                                         size_t cache_entries,
                                         size_t data_blocks) {
   MemLayout layout(shmem_runtime->SharedMutexSize(), cache_entries,
                    data_blocks);
   return layout.metadata_bytes + data_blocks * kBlockSize;
 }

 template<size_t kBlockSize>
 int Sector<kBlockSize>::AllocBlocksFromFreeList(int goal,
                                                 BlockVector* blocks) {
   int allocated = 0;
   while ((allocated < goal) &&
           (sector_header_->free_list_front != kInvalidBlock)) {
     int block_num = sector_header_->free_list_front;
     sector_header_->free_list_front = GetBlockSuccessor(block_num);
     blocks->push_back(block_num);
     ++allocated;
   }
   sector_header_->stats.used_blocks += allocated;
   return allocated;
 }

 template<size_t kBlockSize>
 void Sector<kBlockSize>::ReturnBlocksToFreeList(const BlockVector& blocks) {
   for (size_t c = 0; c < blocks.size(); ++c) {
     BlockNum block_num = blocks[c];
     SetBlockSuccessor(block_num, sector_header_->free_list_front);
     sector_header_->free_list_front = block_num;
   }
   sector_header_->stats.used_blocks -= blocks.size();
 }

 template<size_t kBlockSize>
 void Sector<kBlockSize>::InsertEntryIntoLRU(EntryNum entry_num) {
   CacheEntry* entry = EntryAt(entry_num);
   CHECK((entry->lru_prev == kInvalidEntry) &&
         (entry->lru_next == kInvalidEntry));
   ++sector_header_->stats.used_entries;
   entry->lru_next = sector_header_->lru_list_front;
   if (entry->lru_next == kInvalidEntry) {
     sector_header_->lru_list_rear = entry_num;
   } else {
     EntryAt(entry->lru_next)->lru_prev = entry_num;
   }
   sector_header_->lru_list_front = entry_num;
 }

 template<size_t kBlockSize>
 void Sector<kBlockSize>::UnlinkEntryFromLRU(int entry_num) {
   CacheEntry* entry = EntryAt(entry_num);

   // TODO(morlovich): again, perhaps a bit too much work for stats.
   if (entry->lru_next != kInvalidEntry ||
       entry->lru_prev != kInvalidEntry ||
       sector_header_->lru_list_front == entry_num) {
     --sector_header_->stats.used_entries;
   }

   // Update successor or rear pointer.
   if (entry->lru_next == kInvalidEntry) {
     // Either at end or not linked-in at all.
     if (entry_num == sector_header_->lru_list_rear) {
       sector_header_->lru_list_rear = entry->lru_prev;
     }
   } else {
     EntryAt(entry->lru_next)->lru_prev = entry->lru_prev;
   }

   // Update predecessor or front pointer.
   if (entry->lru_prev == kInvalidEntry) {
     // Front or not linked-in at all.
     if (entry_num == sector_header_->lru_list_front) {
       sector_header_->lru_list_front = entry->lru_next;
     }
   } else {
     EntryAt(entry->lru_prev)->lru_next = entry->lru_next;
   }

   // clear own links.
   entry->lru_prev = kInvalidEntry;
   entry->lru_next = kInvalidEntry;
 }

 template<size_t kBlockSize>
 size_t Sector<kBlockSize>::BytesInPortion(size_t total_bytes, size_t b,
                                           size_t total) {
   if (b != (total -1)) {
     return kBlockSize;
   } else {
     size_t rem = total_bytes % kBlockSize;
     return (rem == 0) ? kBlockSize : rem;
   }
 }

 template<size_t kBlockSize>
 int Sector<kBlockSize>::BlockListForEntry(CacheEntry* entry,
                                           BlockVector* out_blocks) {
   int data_blocks = DataBlocksForSize(entry->byte_size);

   BlockNum block = entry->first_block;
   for (int d = 0; d < data_blocks; ++d) {
     DCHECK_LE(0, block);
     DCHECK_LT(block, static_cast<BlockNum>(data_blocks_));
     out_blocks->push_back(block);
     block = GetBlockSuccessor(block);
   }
   DCHECK_EQ(block, kInvalidBlock);

   return data_blocks;
 }

 SectorStats::SectorStats()
     : num_put(0),
       num_put_update(0),
       num_put_replace(0),
       num_put_concurrent_create(0),
       num_put_concurrent_full_set(0),
       num_put_spins(0),
       num_get(0),
       num_get_hit(0),
       used_entries(0),
       used_blocks(0) {
 }

 void SectorStats::Add(const SectorStats& other) {
   num_put += other.num_put;
   num_put_update += other.num_put_update;
   num_put_replace += other.num_put_replace;
   num_put_concurrent_create += other.num_put_concurrent_create;
   num_put_concurrent_full_set += other.num_put_concurrent_full_set;
   num_put_spins += other.num_put_spins;
   num_get += other.num_get;
   num_get_hit += other.num_get_hit;
   used_entries += other.used_entries;
   used_blocks += other.used_blocks;
 }

 GoogleString SectorStats::Dump(size_t total_entries,
                                size_t total_blocks) const {
   GoogleString out;
   StringAppendF(&out, "Total put operations: %s\n",
                 Integer64ToString(num_put).c_str());
   StringAppendF(&out, "  updating an existing key: %s\n",
                 Integer64ToString(num_put_update).c_str());
   StringAppendF(&out, "  replace/conflict miss: %s\n",
                 Integer64ToString(num_put_replace).c_str());
   StringAppendF(
       &out, "  simultaneous same-key insert: %s\n",
       Integer64ToString(num_put_concurrent_create).c_str());
   StringAppendF(
       &out, "  dropped since all of associativity set locked: %s\n",
       Integer64ToString(num_put_concurrent_full_set).c_str());
   StringAppendF(
       &out, "  spinning sleeps performed by writers: %s\n",
       Integer64ToString(num_put_spins).c_str());

   StringAppendF(&out, "Total get operations: %s\n",
                 Integer64ToString(num_get).c_str());
   StringAppendF(&out, "  hits: %s (%.2f%%)\n",
                 Integer64ToString(num_get_hit).c_str(),
                 percent(num_get_hit, num_get));

   StringAppendF(&out, "Entries used: %s (%.2f%%)\n",
                 Integer64ToString(used_entries).c_str(),
                 percent(used_entries, total_entries));
   StringAppendF(&out, "Blocks used: %s (%.2f%%)\n",
                 Integer64ToString(used_blocks).c_str(),
                 percent(used_blocks, total_blocks));
   return out;
 }

 template<size_t kBlockSize>
 void Sector<kBlockSize>::DumpStats(MessageHandler* handler) {
   mutex()->Lock();
   GoogleString dump = sector_stats()->Dump(cache_entries_, data_blocks_);
   mutex()->Unlock();
   handler->MessageS(kError, dump);
 }

 template class Sector<64>;
 template class Sector<512>;
 template class Sector<4096>;

 }  // namespace SharedMemCacheData

 }  // namespace net_instaweb
	/*
	* Copyright 2011 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	// Author: morlovich@google.com (Maksim Orlovich)

	// Data structure operation helpers for SharedMemCache. See the top of
	// shared_mem_cache.cc for data format descriptions.

	#include "pagespeed/kernel/sharedmem/shared_mem_cache_data.h"

	#include "base/logging.h"
	#include "pagespeed/kernel/base/abstract_mutex.h"
	#include "pagespeed/kernel/base/abstract_shared_mem.h"
	#include "pagespeed/kernel/base/message_handler.h"
	#include "pagespeed/kernel/base/string_util.h"

	namespace net_instaweb {

	namespace SharedMemCacheData {

	namespace {
	// Assumes align is power-of-2
	inline size_t AlignTo(size_t alignment, size_t in) {
	return (in + (alignment - 1)) & ~(alignment - 1);
	}

	double percent(int64 portion, int64 total) {
	return static_cast<double>(portion) / static_cast<double>(total) * 100.0;
	}

	} // namespace

	template<size_t kBlockSize>
	struct Sector<kBlockSize>::MemLayout {
	MemLayout(size_t mutex_size, size_t cache_entries, size_t data_blocks) {
	// Check out alignment assumptions -- everything must be of a size
	// that's multiple of 8. The exact sizes don't matter too much, but
	// we check it anyway to avoid surprises.
	CHECK_EQ(96u, sizeof(SectorHeader));
	CHECK_EQ(48u, sizeof(CacheEntry));

	header_bytes = AlignTo(8, sizeof(SectorHeader) + mutex_size);
	block_successor_list_bytes =
	AlignTo(8, sizeof(BlockNum) * data_blocks);
	size_t directory_size = sizeof(CacheEntry) * cache_entries;
	metadata_bytes =
	AlignTo(kBlockSize,
	header_bytes + directory_size + block_successor_list_bytes);
	}

	size_t header_bytes; // also offset to the block successor list.
	size_t block_successor_list_bytes;
	size_t metadata_bytes; // e.g. offset to the blocks.
	};

	template<size_t kBlockSize>
	Sector<kBlockSize>::Sector(AbstractSharedMemSegment* segment,
	size_t sector_offset, size_t cache_entries,
	size_t data_blocks)
	: cache_entries_(cache_entries),
	data_blocks_(data_blocks),
	segment_(segment),
	sector_offset_(sector_offset) {
	MemLayout layout(segment->SharedMutexSize(), cache_entries, data_blocks);
	char* base = const_cast<char*>(segment->Base()) + sector_offset;
	sector_header_ = reinterpret_cast<SectorHeader*>(base);
	block_successors_ = reinterpret_cast<BlockNum*>(base + layout.header_bytes);
	directory_base_ =
	base + layout.header_bytes + layout.block_successor_list_bytes;
	blocks_base_ = base + layout.metadata_bytes;
	}

	template<size_t kBlockSize>
	Sector<kBlockSize>::~Sector() {
	}

	template<size_t kBlockSize>
	bool Sector<kBlockSize>::Attach(MessageHandler* handler) {
	mutex_.reset(
	segment_->AttachToSharedMutex(sector_offset_ + sizeof(SectorHeader)));
	return (mutex_.get() != NULL);
	}

	template<size_t kBlockSize>
	bool Sector<kBlockSize>::Initialize(MessageHandler* handler)
	NO_THREAD_SAFETY_ANALYSIS {
	if (!segment_->InitializeSharedMutex(sector_offset_ + sizeof(SectorHeader),
	handler)) {
	return false;
	}

	// Connect to the mutex, now it's created.
	if (!Attach(handler)) {
	return false;
	}

	// Initialize the LRU and the cache entry.
	sector_header_->lru_list_front = kInvalidEntry;
	sector_header_->lru_list_rear = kInvalidEntry;
	for (size_t c = 0; c < cache_entries_; ++c) {
	CacheEntry* entry = EntryAt(c);
	entry->lru_prev = kInvalidEntry;
	entry->lru_next = kInvalidEntry;
	entry->first_block = kInvalidBlock;
	}

	// Initialize the freelist and block successor list.
	sector_header_->free_list_front = kInvalidBlock;
	BlockVector all_blocks;
	for (size_t c = 0; c < data_blocks_; ++c) {
	all_blocks.push_back(static_cast<BlockNum>(c));
	}
	ReturnBlocksToFreeList(all_blocks);
	sector_header_->stats.used_blocks = 0;

	return true;
	}

	template<size_t kBlockSize>
	size_t Sector<kBlockSize>::RequiredSize(AbstractSharedMem* shmem_runtime,
	size_t cache_entries,
	size_t data_blocks) {
	MemLayout layout(shmem_runtime->SharedMutexSize(), cache_entries,
	data_blocks);
	return layout.metadata_bytes + data_blocks * kBlockSize;
	}

	template<size_t kBlockSize>
	int Sector<kBlockSize>::AllocBlocksFromFreeList(int goal,
	BlockVector* blocks) {
	int allocated = 0;
	while ((allocated < goal) &&
	(sector_header_->free_list_front != kInvalidBlock)) {
	int block_num = sector_header_->free_list_front;
	sector_header_->free_list_front = GetBlockSuccessor(block_num);
	blocks->push_back(block_num);
	++allocated;
	}
	sector_header_->stats.used_blocks += allocated;
	return allocated;
	}

	template<size_t kBlockSize>
	void Sector<kBlockSize>::ReturnBlocksToFreeList(const BlockVector& blocks) {
	for (size_t c = 0; c < blocks.size(); ++c) {
	BlockNum block_num = blocks[c];
	SetBlockSuccessor(block_num, sector_header_->free_list_front);
	sector_header_->free_list_front = block_num;
	}
	sector_header_->stats.used_blocks -= blocks.size();
	}

	template<size_t kBlockSize>
	void Sector<kBlockSize>::InsertEntryIntoLRU(EntryNum entry_num) {
	CacheEntry* entry = EntryAt(entry_num);
	CHECK((entry->lru_prev == kInvalidEntry) &&
	(entry->lru_next == kInvalidEntry));
	++sector_header_->stats.used_entries;
	entry->lru_next = sector_header_->lru_list_front;
	if (entry->lru_next == kInvalidEntry) {
	sector_header_->lru_list_rear = entry_num;
	} else {
	EntryAt(entry->lru_next)->lru_prev = entry_num;
	}
	sector_header_->lru_list_front = entry_num;
	}

	template<size_t kBlockSize>
	void Sector<kBlockSize>::UnlinkEntryFromLRU(int entry_num) {
	CacheEntry* entry = EntryAt(entry_num);

	// TODO(morlovich): again, perhaps a bit too much work for stats.
	if (entry->lru_next != kInvalidEntry \|\|
	entry->lru_prev != kInvalidEntry \|\|
	sector_header_->lru_list_front == entry_num) {
	--sector_header_->stats.used_entries;
	}

	// Update successor or rear pointer.
	if (entry->lru_next == kInvalidEntry) {
	// Either at end or not linked-in at all.
	if (entry_num == sector_header_->lru_list_rear) {
	sector_header_->lru_list_rear = entry->lru_prev;
	}
	} else {
	EntryAt(entry->lru_next)->lru_prev = entry->lru_prev;
	}

	// Update predecessor or front pointer.
	if (entry->lru_prev == kInvalidEntry) {
	// Front or not linked-in at all.
	if (entry_num == sector_header_->lru_list_front) {
	sector_header_->lru_list_front = entry->lru_next;
	}
	} else {
	EntryAt(entry->lru_prev)->lru_next = entry->lru_next;
	}

	// clear own links.
	entry->lru_prev = kInvalidEntry;
	entry->lru_next = kInvalidEntry;
	}

	template<size_t kBlockSize>
	size_t Sector<kBlockSize>::BytesInPortion(size_t total_bytes, size_t b,
	size_t total) {
	if (b != (total -1)) {
	return kBlockSize;
	} else {
	size_t rem = total_bytes % kBlockSize;
	return (rem == 0) ? kBlockSize : rem;
	}
	}

	template<size_t kBlockSize>
	int Sector<kBlockSize>::BlockListForEntry(CacheEntry* entry,
	BlockVector* out_blocks) {
	int data_blocks = DataBlocksForSize(entry->byte_size);

	BlockNum block = entry->first_block;
	for (int d = 0; d < data_blocks; ++d) {
	DCHECK_LE(0, block);
	DCHECK_LT(block, static_cast<BlockNum>(data_blocks_));
	out_blocks->push_back(block);
	block = GetBlockSuccessor(block);
	}
	DCHECK_EQ(block, kInvalidBlock);

	return data_blocks;
	}

	SectorStats::SectorStats()
	: num_put(0),
	num_put_update(0),
	num_put_replace(0),
	num_put_concurrent_create(0),
	num_put_concurrent_full_set(0),
	num_put_spins(0),
	num_get(0),
	num_get_hit(0),
	used_entries(0),
	used_blocks(0) {
	}

	void SectorStats::Add(const SectorStats& other) {
	num_put += other.num_put;
	num_put_update += other.num_put_update;
	num_put_replace += other.num_put_replace;
	num_put_concurrent_create += other.num_put_concurrent_create;
	num_put_concurrent_full_set += other.num_put_concurrent_full_set;
	num_put_spins += other.num_put_spins;
	num_get += other.num_get;
	num_get_hit += other.num_get_hit;
	used_entries += other.used_entries;
	used_blocks += other.used_blocks;
	}

	GoogleString SectorStats::Dump(size_t total_entries,
	size_t total_blocks) const {
	GoogleString out;
	StringAppendF(&out, "Total put operations: %s\n",
	Integer64ToString(num_put).c_str());
	StringAppendF(&out, " updating an existing key: %s\n",
	Integer64ToString(num_put_update).c_str());
	StringAppendF(&out, " replace/conflict miss: %s\n",
	Integer64ToString(num_put_replace).c_str());
	StringAppendF(
	&out, " simultaneous same-key insert: %s\n",
	Integer64ToString(num_put_concurrent_create).c_str());
	StringAppendF(
	&out, " dropped since all of associativity set locked: %s\n",
	Integer64ToString(num_put_concurrent_full_set).c_str());
	StringAppendF(
	&out, " spinning sleeps performed by writers: %s\n",
	Integer64ToString(num_put_spins).c_str());

	StringAppendF(&out, "Total get operations: %s\n",
	Integer64ToString(num_get).c_str());
	StringAppendF(&out, " hits: %s (%.2f%%)\n",
	Integer64ToString(num_get_hit).c_str(),
	percent(num_get_hit, num_get));

	StringAppendF(&out, "Entries used: %s (%.2f%%)\n",
	Integer64ToString(used_entries).c_str(),
	percent(used_entries, total_entries));
	StringAppendF(&out, "Blocks used: %s (%.2f%%)\n",
	Integer64ToString(used_blocks).c_str(),
	percent(used_blocks, total_blocks));
	return out;
	}

	template<size_t kBlockSize>
	void Sector<kBlockSize>::DumpStats(MessageHandler* handler) {
	mutex()->Lock();
	GoogleString dump = sector_stats()->Dump(cache_entries_, data_blocks_);
	mutex()->Unlock();
	handler->MessageS(kError, dump);
	}

	template class Sector<64>;
	template class Sector<512>;
	template class Sector<4096>;

	} // namespace SharedMemCacheData

	} // namespace net_instaweb