summaryrefslogtreecommitdiffstats
path: root/client/glz_decoder_window.cpp
blob: 24dfce3eca7ef9813ac11787cfde5d3957354179 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
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
151
152
153
154
155
156
157
158
159
160
161
162
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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
/*
   Copyright (C) 2009 Red Hat, Inc.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, see <http://www.gnu.org/licenses/>.
*/

#include "common.h"

#include "glz_decoder_window.h"
#include "utils.h"

#define INIT_IMAGES_CAPACITY 100
#define WIN_OVERFLOW_FACTOR 1.5
#define WIN_REALLOC_FACTOR 1.5

GlzDecoderWindow::GlzDecoderWindow(int pixels_capacity, GlzDecoderDebug &debug_calls)
    : _pixels_capacity (pixels_capacity)
    , _aborting (false)
    , _debug_calls (debug_calls)
{
    if (_pixels_capacity > LZ_MAX_WINDOW_SIZE) {
        std::string erro_str;
        string_printf(erro_str, "Glz Window capacity exceeds the limit %d",
                      _pixels_capacity);
        _debug_calls.error(erro_str);
    }

    _images_capacity = INIT_IMAGES_CAPACITY;
    _images = new  GlzDecodedImage*[_images_capacity];
    if (!_images) {
        _debug_calls.error(std::string("failed allocating images\n"));
    }

    memset(_images, 0, sizeof(GlzDecodedImage*) * _images_capacity);

    init();
}

GlzDecoderWindow::~GlzDecoderWindow()
{
    clear();
    delete[] _images;
}

DecodedImageWinId GlzDecoderWindow::pre_decode(uint64_t image_id, uint64_t relative_head_id)
{
    DecodedImageWinId image_win_id = pre_decode_update_window(image_id, relative_head_id);
    pre_decode_finalize();
    return image_win_id;
}

void GlzDecoderWindow::post_decode(GlzDecodedImage *image)
{
    post_decode_intialize();
    post_decode_update_window(image);
}

/* index: the physical index in the images array. Note that it can't change between waits since
   the realloc mutex should be read locked.
   No starvation for the realloc mutex can occur, since the image we wait for is located before us,
   hence, when it arrives - no realloc is needed. */
void GlzDecoderWindow::wait_for_image(int index)
{
    Lock lock(_new_image_mutex);
    GlzDecodedImage *image = _images[index]; // can be performed without locking the _win_mutex,
                                             // since it is called after pre and the rw mutex is                                                 // locked, hence, physical changes to the window are
                                             // not allowed. In addition the reading of the image ptr
                                             // is atomic, thus, even if the value changes we are
                                             // not affected.

    while (!image) {
        if (_aborting) {
            THROW("aborting");
        }
        _new_image_cond.wait(lock);
        image = _images[index];
    }
}

void GlzDecoderWindow::abort()
{
    Lock lock1(_win_modifiers_mutex);
    Lock lock2(_new_image_mutex);
    _aborting = true;
    _new_image_cond.notify_all();
    _release_image_cond.notify_all();
    _win_alloc_cond.notify_all();
}

void GlzDecoderWindow::clear()
{
    Lock lock(_win_modifiers_mutex);
    release_images();
    init();
}

void GlzDecoderWindow::set_pixels_capacity(int pixels_capacity)
{
    Lock lock(_win_modifiers_mutex);

    if (pixels_capacity > LZ_MAX_WINDOW_SIZE) {
        std::string erro_str;
        string_printf(erro_str, "Glz Window capacity exceeds the limit %d",
                      pixels_capacity);
        _debug_calls.error(erro_str);
    }
    _pixels_capacity = pixels_capacity;
}

void GlzDecoderWindow::init()
{
    _missing_list.clear();
    // The window is never empty: the head is in the missing list or in the window.
    // The first missing image is 0.
    _missing_list.push_front(0);
    _head_idx = 0;
    _tail_image_id = 0;
    _n_images = 1;
    _n_pixels = 0;
}

void GlzDecoderWindow::release_images()
{
    for (int i = 0; i < _n_images; i++) {
        int idx = (_head_idx + i) % _images_capacity;
        if (_images[idx]) {
            delete _images[idx];
            _images[idx] = NULL;
        }
    }
}

inline bool GlzDecoderWindow::is_empty()
{
    return (!_n_images);
}

/* approximated overflow. Considers only the size that currently occupies the window and
   not the size of the missing images. TODO: consider other measures */
inline bool GlzDecoderWindow::will_overflow(uint64_t image_id, uint64_t relative_head_id)
{
    if (image_id <= _tail_image_id) {
        return false;
    }

    if (_n_pixels > (WIN_OVERFLOW_FACTOR * _pixels_capacity)) {
        return true;
    }

    if (!_missing_list.empty() && (_missing_list.front() < relative_head_id)) {
        // two non overlapping windows
        return true;
    }

    return false;
}

DecodedImageWinId GlzDecoderWindow::pre_decode_update_window(uint64_t image_id,
                                                             uint64_t relative_head_id)
{
    Lock lock(_win_modifiers_mutex);
    int realloc_size;

    while (will_overflow(image_id, relative_head_id)) {
        if (_aborting) {
            THROW("aborting");
        }
        _release_image_cond.wait(lock);
    }

    // The following conditions prevent starvation in case thread (1) should realloc,
    // thread (2) is during decode and waits for a previous image and
    /// thread (3) should decode this the previous image and needs to enter pre decode although
    // (1) is in there.
    // We must give priority to older images in the window.
    // The condition should be checked over again in case a later image entered the window
    // and the realocation was already performed
    while ((realloc_size = calc_realloc_size(image_id))) {
        if (_aborting) {
            THROW("aborting");
        }

        if (_win_alloc_rw_mutex.try_write_lock()) {
            realloc(realloc_size);
            _win_alloc_rw_mutex.write_unlock();
            break;
        } else {
            _win_alloc_cond.wait(lock);
        }
    }

    if (image_id > _tail_image_id) { // not in missing list
        add_pre_decoded_image(image_id);
    }

    return calc_image_win_idx(image_id);
}

void GlzDecoderWindow::add_pre_decoded_image(uint64_t image_id)
{
    GLZ_ASSERT(_debug_calls, image_id > _tail_image_id);
    GLZ_ASSERT(_debug_calls, image_id - _tail_image_id + _n_images < _images_capacity);

    for (uint64_t miss_id = _tail_image_id + 1; miss_id <= image_id; miss_id++) {
        _missing_list.push_back(miss_id);
        _n_images++;
    }
    _tail_image_id = image_id;
}

inline int GlzDecoderWindow::calc_realloc_size(uint64_t new_tail_image_id)
{
    if (new_tail_image_id <= _tail_image_id) {
        return 0;
    }

    int min_capacity = (int)(_n_images + new_tail_image_id - _tail_image_id);

    if ((min_capacity * WIN_REALLOC_FACTOR) > _images_capacity) {
        return (int)MAX(min_capacity * WIN_REALLOC_FACTOR, WIN_REALLOC_FACTOR * _images_capacity);
    } else {
        return 0;
    }
}

void GlzDecoderWindow::realloc(int size)
{
    GlzDecodedImage **new_images = new GlzDecodedImage*[size];

    if (!new_images) {
        _debug_calls.error(std::string("failed allocating images array"));
    }
    memset(new_images, 0, sizeof(GlzDecodedImage*) * size);

    for (int i = 0; i < _n_images; i++) {
        new_images[i] = _images[(i + _head_idx) % _images_capacity];
    }
    delete[] _images;

    _images = new_images;
    _head_idx = 0;
    _images_capacity = size;
}

void GlzDecoderWindow::pre_decode_finalize()
{
    _win_alloc_rw_mutex.read_lock();
}

void GlzDecoderWindow::post_decode_intialize()
{
    _win_alloc_rw_mutex.read_unlock();
}

void GlzDecoderWindow::post_decode_update_window(GlzDecodedImage *image)
{
    Lock lock(_win_modifiers_mutex);
    add_decoded_image(image);
    narrow_window(image);
    _win_alloc_cond.notify_all();
}

void GlzDecoderWindow::add_decoded_image(GlzDecodedImage *image)
{
    Lock lock(_new_image_mutex);
    GLZ_ASSERT(_debug_calls, image->get_id() <= _tail_image_id);
    _images[calc_image_win_idx(image->get_id())] = image;
    _n_pixels += image->get_size();
    _new_image_cond.notify_all();
}

/* Important observations:
   1) When an image is added, if it is not the first missing image, it is not removed
      immediately from the missing list (in order not to store another pointer to
      the missing list inside the window ,or otherwise, to go over the missing list
      and look for the image).
   2) images that weren't removed from the missing list in their addition time, will be removed when
      preliminary images will be added.
   3) The first item in the missing list is always really missing.
   4) The missing list is always ordered by image id (see add_pre_decoded_image)
*/
void GlzDecoderWindow::narrow_window(GlzDecodedImage *last_added)
{
    uint64_t new_head_image_id;

    GLZ_ASSERT(_debug_calls, !_missing_list.empty());

    if (_missing_list.front() != last_added->get_id()) {
        return;
    }

    _missing_list.pop_front();  // removing the last added image from the missing list

    /* maintaining the missing list: removing front images that already arrived */
    while (!_missing_list.empty()) {
        int front_win_idx = calc_image_win_idx(_missing_list.front());
        if (_images[front_win_idx] == NULL) { // still missing
            break;
        } else {
            _missing_list.pop_front();
        }
    }

    /* removing unnecessary image from the window's head*/
    if (_missing_list.empty()) {
        new_head_image_id = _images[
                calc_image_win_idx(_tail_image_id)]->get_window_head_id();
    } else {
        // there must be at least one image in the window since narrow_window is called
        // from post decode
        GLZ_ASSERT(_debug_calls, _images[calc_image_win_idx(_missing_list.front() - 1)]);
        new_head_image_id = _images[
                calc_image_win_idx(_missing_list.front() - 1)]->get_window_head_id();
    }

    remove_head(new_head_image_id);
}

inline void GlzDecoderWindow::remove_head(uint64_t new_head_image_id)
{
    GLZ_ASSERT(_debug_calls, _images[_head_idx]);

    int n_images_remove = (int)(new_head_image_id - _images[_head_idx]->get_id());

    if (!n_images_remove) {
        return;
    }

    for (int i = 0; i < n_images_remove; i++) {
        int index = (_head_idx + i) % _images_capacity;
        _n_pixels -= _images[index]->get_size();
        delete _images[index];
        _images[index] = NULL;
    }

    _n_images -= n_images_remove;
    _head_idx = (_head_idx + n_images_remove) % _images_capacity;

    _release_image_cond.notify_all();
}

/* NOTE: can only be used when the window is locked. (i.e, not inside get_ref_pixel) */
inline int GlzDecoderWindow::calc_image_win_idx(uint64_t image_id)
{
    return (int)((_head_idx + _n_images - 1 - (_tail_image_id - image_id)) % _images_capacity);
}