Class: PEROBS::SpaceManager

Inherits:
Object
  • Object
show all
Defined in:
lib/perobs/SpaceManager.rb

Overview

The SpaceManager is used to keep a list of all the empty spaces in a FlatFileDB file. An empty space is described by its starting address and its length in bytes. The SpaceManager keeps a list of all the spaces and can find the best fit space when a new blob needs to be added to the FlatFileDB.

The SpaceManager uses two files to store the list. The first is a file with the actual addresses. This is a set of linked address lists. Each list holds the addresses for spaces that have exactly the same size. The second file is a BTree file that serves as the index. It is used to map the length of a space to the address of the linked list for that particular length. The linked list consists of elements that only hold 2 items. The actual address in the FlatFileDB and the address of the next entry in the linked list in the list file.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(db_dir, progressmeter, btree_order = 65) ⇒ SpaceManager

Returns a new instance of SpaceManager.



53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/perobs/SpaceManager.rb', line 53

def initialize(db_dir, progressmeter, btree_order = 65)
  @db_dir = db_dir
  @progressmeter = progressmeter

  @index = BTree.new(@db_dir, 'space_index', btree_order, @progressmeter)
  # The space list contains blobs that have each 2 entries. The address of
  # the space in the FlatFile and the address of the next blob in the
  # space list file that is an entry for the same space size. An address
  # of 0 marks the end of the list.
  @list = EquiBlobsFile.new(@db_dir, 'space_list', @progressmeter, 2 * 8, 1)
end

Instance Attribute Details

#added_spaces ⇒ Object (readonly)

Returns the value of attribute added_spaces.



51
52
53
 
# File 'lib/perobs/SpaceManager.rb', line 51

def added_spaces
  @added_spaces
end

#failed_requests ⇒ Object (readonly)

Returns the value of attribute failed_requests.



51
52
53
 
# File 'lib/perobs/SpaceManager.rb', line 51

def failed_requests
  @failed_requests
end

#recycled_spaces ⇒ Object (readonly)

Returns the value of attribute recycled_spaces.



51
52
53
 
# File 'lib/perobs/SpaceManager.rb', line 51

def recycled_spaces
  @recycled_spaces
end

Instance Method Details

#add_space(address, length) ⇒ Object 



93
94
95
96
97
98
99
100
101
102
 
# File 'lib/perobs/SpaceManager.rb', line 93

def add_space(address, length)
  if (list_entry_addr = @index.get(length))
    # There is already at least one move entry for this length.
    new_list_entry_addr = insert_space_in_list(address, list_entry_addr)
  else
    new_list_entry_addr = insert_space_in_list(address, 0)
  end
  @index.insert(length, new_list_entry_addr)
  @added_spaces += 1
end

#check(flat_file = nil) ⇒ Object 



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 
# File 'lib/perobs/SpaceManager.rb', line 163

def check(flat_file = nil)
  sync
  return false unless @index.check
  return false unless @list.check

  smallest_space = nil
  largest_space = nil
  total_space_bytes = 0
  space_distribution = ::Hash.new(0)

  @index.each do |length, list_entry_addr|
    if list_entry_addr <= 0
      PEROBS.log.error "list_entry_addr (#{list_entry_addr}) " +
        "must be positive"
      return false
    end

    # Detect smallest and largest space
    if smallest_space.nil? || length < smallest_space
      smallest_space = length
    end
    if largest_space.nil? || length > largest_space
      largest_space = length
    end

    known_addresses = [ list_entry_addr ]
    entries = 0
    while list_entry_addr > 0
      entries += 1
      unless (blob = @list.retrieve_blob(list_entry_addr))
        PEROBS.log.error "SpaceManager points to non-existing " +
          "space list entry at address #{list_entry_addr}"
        return false
      end
      space_address, next_entry_addr = blob.unpack('QQ')

      if known_addresses.include?(next_entry_addr)
        PEROBS.log.error "Space list is cyclic: "
          "#{known_addresses + next_entry_addr}"
        return false
      end
      if flat_file &&
          !flat_file.has_space?(space_address, length)
        PEROBS.log.error "SpaceManager has space at offset " +
          "#{space_address} of size #{length} that isn't " +
          "available in the FlatFile."
        return false
      end
      list_entry_addr = next_entry_addr
    end

    total_space_bytes += length * entries
    space_distribution[msb(length)] += entries
  end

  PEROBS.log.info "SpaceManager stats: smallest: #{smallest_space}; " +
    "largest: #{largest_space}; total bytes: #{total_space_bytes}; " +
    "distribution: " +
    "#{space_distribution.map { |l, c| "#{2 ** (l - 1)}-#{2 ** l - 1}:#{c}; " }}"

  true
end

#clear ⇒ Object 



152
153
154
155
156
 
# File 'lib/perobs/SpaceManager.rb', line 152

def clear
  @list.clear
  @index.clear
  reset_stats
end

#close ⇒ Object 



71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/perobs/SpaceManager.rb', line 71

def close
  if @index.is_open?
    PEROBS.log.info "SpaceManager has currently #{@list.total_entries} " +
      "used blobs and #{@list.total_spaces} unused blobs in list " +
      "EquiBlobsFile"
    PEROBS.log.info "#{@added_spaces} were added, #{@recycled_spaces} " +
      "spaces were recycled and #{@failed_requests} requests failed"

    @list.close
    @index.close
  end
end

#erase ⇒ Object 



158
159
160
161
 
# File 'lib/perobs/SpaceManager.rb', line 158

def erase
  @list.erase
  @index.erase
end

#get_space(length) ⇒ Object 



117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/perobs/SpaceManager.rb', line 117

def get_space(length)
  # We use a simple exact fit strategy. All attempts to use a more
  # elaborate scheme were actually less efficient. Non-exact matches
  # generate new spaces for the remainder and fragment the blob file with
  # lots of unusable small spaces. Most applications seem to have
  # clustered their blob sizes around a number of popular sizes. So exact
  # match is very efficient to implement and results in the highest
  # probability that a space will be reused soon.
  list_entry_addr = @index.get(length)

  if list_entry_addr
    blob = @list.retrieve_blob(list_entry_addr)
    space_address, next_entry_addr = blob.unpack('QQ')
    @list.delete_blob(list_entry_addr)

    if next_entry_addr > 0
      # Update the index entry for the length to point to the
      # following space list entry.
      @index.insert(length, next_entry_addr)
    else
      # The space list for this length is empty. Remove the entry
      # from the index.
      @index.remove(length)
    end
    @recycled_spaces += 1

    # We return the length to remain compatible with the old SpaceTree
    # API.
    return [ space_address, length ]
  end

  @failed_requests += 1
  nil
end

#has_space?(address, length) ⇒ Boolean

Returns:

  • (Boolean) 


104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/perobs/SpaceManager.rb', line 104

def has_space?(address, length)
  if (list_entry_addr = @index.get(length))
    while list_entry_addr > 0
      blob = @list.retrieve_blob(list_entry_addr)
      space_address, next_entry_addr = blob.unpack('QQ')
      return true if space_address == address
      list_entry_addr = next_entry_addr
    end
  end

  false
end

#is_open? ⇒ Boolean

Returns:

  • (Boolean) 


84
85
86
 
# File 'lib/perobs/SpaceManager.rb', line 84

def is_open?
  @index.is_open?
end

#open ⇒ Object 



65
66
67
68
69
 
# File 'lib/perobs/SpaceManager.rb', line 65

def open
  @index.open
  @list.open
  reset_stats
end

#sync ⇒ Object 



88
89
90
91
 
# File 'lib/perobs/SpaceManager.rb', line 88

def sync
  @list.sync
  @index.sync
end

#to_a ⇒ Object 



226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
 
# File 'lib/perobs/SpaceManager.rb', line 226

def to_a
  a = []

  @index.each do |length, list_entry_addr|
    while list_entry_addr > 0
      blob = @list.retrieve_blob(list_entry_addr)
      space_address, next_entry_addr = blob.unpack('QQ')

      a << [ space_address, length ]

      list_entry_addr = next_entry_addr
    end
  end

  a.sort { |a, b| a[0] <=> b[0] }
end