1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "content/browser/loader/resource_buffer.h"
6
7#include <math.h>
8
9#include "base/logging.h"
10
11namespace content {
12
13// A circular buffer allocator.
14//
15// We keep track of the starting offset (alloc_start_) and the ending offset
16// (alloc_end_).  There are two layouts to keep in mind:
17//
18// #1:
19//    ------------[XXXXXXXXXXXXXXXXXXXXXXX]----
20//                ^                        ^
21//                start                    end
22//
23// #2:
24//    XXXXXXXXXX]---------------------[XXXXXXXX
25//               ^                    ^
26//               end                  start
27//
28// If end <= start, then we have the buffer wraparound case (depicted second).
29// If the buffer is empty, then start and end will be set to -1.
30//
31// Allocations are always contiguous.
32
33ResourceBuffer::ResourceBuffer()
34    : buf_size_(0),
35      min_alloc_size_(0),
36      max_alloc_size_(0),
37      alloc_start_(-1),
38      alloc_end_(-1) {
39}
40
41ResourceBuffer::~ResourceBuffer() {
42}
43
44bool ResourceBuffer::Initialize(int buffer_size,
45                                int min_allocation_size,
46                                int max_allocation_size) {
47  DCHECK(!IsInitialized());
48
49  // It would be wasteful if these are not multiples of min_allocation_size.
50  DCHECK_EQ(0, buffer_size % min_allocation_size);
51  DCHECK_EQ(0, max_allocation_size % min_allocation_size);
52
53  buf_size_ = buffer_size;
54  min_alloc_size_ = min_allocation_size;
55  max_alloc_size_ = max_allocation_size;
56
57  return shared_mem_.CreateAndMapAnonymous(buf_size_);
58}
59
60bool ResourceBuffer::IsInitialized() const {
61  return shared_mem_.memory() != NULL;
62}
63
64bool ResourceBuffer::ShareToProcess(
65    base::ProcessHandle process_handle,
66    base::SharedMemoryHandle* shared_memory_handle,
67    int* shared_memory_size) {
68  DCHECK(IsInitialized());
69
70  if (!shared_mem_.ShareToProcess(process_handle, shared_memory_handle))
71    return false;
72
73  *shared_memory_size = buf_size_;
74  return true;
75}
76
77bool ResourceBuffer::CanAllocate() const {
78  DCHECK(IsInitialized());
79
80  if (alloc_start_ == -1)
81    return true;
82
83  int diff = alloc_end_ - alloc_start_;
84  if (diff > 0)
85    return (buf_size_ - diff) >= min_alloc_size_;
86
87  return -diff >= min_alloc_size_;
88}
89
90char* ResourceBuffer::Allocate(int* size) {
91  DCHECK(CanAllocate());
92
93  int alloc_offset = 0;
94  int alloc_size;
95
96  if (alloc_start_ == -1) {
97    // This is the first allocation.
98    alloc_start_ = 0;
99    alloc_end_ = buf_size_;
100    alloc_size = buf_size_;
101  } else if (alloc_start_ < alloc_end_) {
102    // Append the next allocation if it fits.  Otherwise, wraparound.
103    //
104    // NOTE: We could look to see if a larger allocation is possible by
105    // wrapping around sooner, but instead we just look to fill the space at
106    // the end of the buffer provided that meets the min_alloc_size_
107    // requirement.
108    //
109    if ((buf_size_ - alloc_end_) >= min_alloc_size_) {
110      alloc_offset = alloc_end_;
111      alloc_size = buf_size_ - alloc_end_;
112      alloc_end_ = buf_size_;
113    } else {
114      // It must be possible to allocate a least min_alloc_size_.
115      DCHECK(alloc_start_ >= min_alloc_size_);
116      alloc_size = alloc_start_;
117      alloc_end_ = alloc_start_;
118    }
119  } else {
120    // This is the wraparound case.
121    DCHECK(alloc_end_ < alloc_start_);
122    alloc_offset = alloc_end_;
123    alloc_size = alloc_start_ - alloc_end_;
124    alloc_end_ = alloc_start_;
125  }
126
127  // Make sure alloc_size does not exceed max_alloc_size_.  We store the
128  // current value of alloc_size, so that we can use ShrinkLastAllocation to
129  // trim it back.  This allows us to reuse the alloc_end_ adjustment logic.
130
131  alloc_sizes_.push(alloc_size);
132
133  if (alloc_size > max_alloc_size_) {
134    alloc_size = max_alloc_size_;
135    ShrinkLastAllocation(alloc_size);
136  }
137
138  *size = alloc_size;
139  return static_cast<char*>(shared_mem_.memory()) + alloc_offset;
140}
141
142int ResourceBuffer::GetLastAllocationOffset() const {
143  DCHECK(!alloc_sizes_.empty());
144  DCHECK(alloc_end_ >= alloc_sizes_.back());
145  return alloc_end_ - alloc_sizes_.back();
146}
147
148void ResourceBuffer::ShrinkLastAllocation(int new_size) {
149  DCHECK(!alloc_sizes_.empty());
150
151  int aligned_size = (new_size / min_alloc_size_) * min_alloc_size_;
152  if (aligned_size < new_size)
153    aligned_size += min_alloc_size_;
154
155  DCHECK_LE(new_size, aligned_size);
156  DCHECK_GE(alloc_sizes_.back(), aligned_size);
157
158  int* last_allocation_size = &alloc_sizes_.back();
159  alloc_end_ -= (*last_allocation_size - aligned_size);
160  *last_allocation_size = aligned_size;
161}
162
163void ResourceBuffer::RecycleLeastRecentlyAllocated() {
164  DCHECK(!alloc_sizes_.empty());
165  int allocation_size = alloc_sizes_.front();
166  alloc_sizes_.pop();
167
168  alloc_start_ += allocation_size;
169  DCHECK(alloc_start_ <= buf_size_);
170
171  if (alloc_start_ == alloc_end_) {
172    DCHECK(alloc_sizes_.empty());
173    alloc_start_ = -1;
174    alloc_end_ = -1;
175  } else if (alloc_start_ == buf_size_) {
176    DCHECK(!alloc_sizes_.empty());
177    alloc_start_ = 0;
178  }
179}
180
181}  // namespace content
182