← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to grub-core/lib/relocator.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Robert Millan, Updated translations
  • Date: 2010-11-22 12:24:56 UTC
  • mfrom: (1.26.4 upstream) (17.3.36 sid)
  • mto: (17.3.43 sid)
  • mto: This revision was merged to the branch mainline in revision 89.
  • Revision ID: james.westby@ubuntu.com-20101122122456-y82z3sfb7k4zfdcc
Tags: 1.99~20101122-1
http://bugs.debian.org/550658
http://bugs.debian.org/550702
http://bugs.debian.org/591416
http://bugs.debian.org/593347
http://bugs.debian.org/551627
http://bugs.debian.org/589325
http://bugs.debian.org/543924
http://bugs.debian.org/603354
http://bugs.debian.org/604003
http://bugs.debian.org/604102
[ Colin Watson ]
* New Bazaar snapshot.  Too many changes to list in full, but some of the
  more user-visible ones are as follows:
  - GRUB script:
    + Function parameters, "break", "continue", "shift", "setparams",
      "return", and "!".
    + "export" command supports multiple variable names.
    + Multi-line quoted strings support.
    + Wildcard expansion.
  - sendkey support.
  - USB hotunplugging and USB serial support.
  - Rename CD-ROM to cd on BIOS.
  - Add new --boot-directory option to grub-install, grub-reboot, and
    grub-set-default; the old --root-directory option is still accepted
    but was often confusing.
  - Basic btrfs detection/UUID support (but no file reading yet).
  - bash-completion for utilities.
  - If a device is listed in device.map, always assume that it is
    BIOS-visible rather than using extra layers such as LVM or RAID.
  - Add grub-mknetdir script (closes: #550658).
  - Remove deprecated "root" command.
  - Handle RAID devices containing virtio components.
  - GRUB Legacy configuration file support (via grub-menulst2cfg).
  - Keyboard layout support (via grub-mklayout and grub-kbdcomp).
  - Check generated grub.cfg for syntax errors before saving.
  - Pause execution for at most ten seconds if any errors are displayed,
    so that the user has a chance to see them.
  - Support submenus.
  - Write embedding zone using Reed-Solomon, so that it's robust against
    being partially overwritten (closes: #550702, #591416, #593347).
  - GRUB_DISABLE_LINUX_RECOVERY and GRUB_DISABLE_NETBSD_RECOVERY merged
    into a single GRUB_DISABLE_RECOVERY variable.
  - Fix loader memory allocation failure (closes: #551627).
  - Don't call savedefault on recovery entries (closes: #589325).
  - Support triple-indirect blocks on ext2 (closes: #543924).
  - Recognise DDF1 fake RAID (closes: #603354).

[ Robert Millan ]
* Use dpkg architecture wildcards.

[ Updated translations ]
* Slovenian (Vanja Cvelbar).  Closes: #604003
* Dzongkha (dawa pemo via Tenzin Dendup).  Closes: #604102

Show diffs side-by-side

added added

removed removed

Lines of Context:
grub-core/lib/relocator.c
 
1
/*
 
2
 *  GRUB  --  GRand Unified Bootloader
 
3
 *  Copyright (C) 2009, 2010  Free Software Foundation, Inc.
 
4
 *
 
5
 *  GRUB is free software: you can redistribute it and/or modify
 
6
 *  it under the terms of the GNU General Public License as published by
 
7
 *  the Free Software Foundation, either version 3 of the License, or
 
8
 *  (at your option) any later version.
 
9
 *
 
10
 *  GRUB is distributed in the hope that it will be useful,
 
11
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 *  GNU General Public License for more details.
 
14
 *
 
15
 *  You should have received a copy of the GNU General Public License
 
16
 *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
 
17
 */
 
18
 
 
19
#include <grub/relocator.h>
 
20
#include <grub/relocator_private.h>
 
21
#include <grub/mm_private.h>
 
22
#include <grub/misc.h>
 
23
#include <grub/cache.h>
 
24
#include <grub/memory.h>
 
25
 
 
26
struct grub_relocator
 
27
{
 
28
  struct grub_relocator_chunk *chunks;
 
29
  grub_phys_addr_t postchunks;
 
30
  grub_phys_addr_t highestaddr;
 
31
  grub_phys_addr_t highestnonpostaddr;
 
32
  grub_size_t relocators_size;
 
33
};
 
34
 
 
35
struct grub_relocator_subchunk
 
36
{
 
37
  enum {CHUNK_TYPE_IN_REGION, CHUNK_TYPE_REGION_START,
 
38
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
39
        CHUNK_TYPE_FIRMWARE, CHUNK_TYPE_LEFTOVER
 
40
#endif
 
41
  } type;
 
42
  grub_mm_region_t reg;
 
43
  grub_phys_addr_t start;
 
44
  grub_size_t size;
 
45
  grub_size_t pre_size;
 
46
  struct grub_relocator_extra_block *extra;
 
47
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
48
  struct grub_relocator_fw_leftover *pre, *post;
 
49
#endif
 
50
};
 
51
 
 
52
struct grub_relocator_chunk
 
53
{
 
54
  struct grub_relocator_chunk *next;
 
55
  grub_phys_addr_t src;
 
56
  void *srcv;
 
57
  grub_phys_addr_t target;
 
58
  grub_size_t size;
 
59
  struct grub_relocator_subchunk *subchunks;
 
60
  unsigned nsubchunks;
 
61
};
 
62
 
 
63
struct grub_relocator_extra_block
 
64
{
 
65
  struct grub_relocator_extra_block *next;
 
66
  struct grub_relocator_extra_block **prev;
 
67
  grub_phys_addr_t start;
 
68
  grub_phys_addr_t end;
 
69
};
 
70
 
 
71
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
72
struct grub_relocator_fw_leftover
 
73
{
 
74
  struct grub_relocator_fw_leftover *next;
 
75
  struct grub_relocator_fw_leftover **prev;
 
76
  grub_phys_addr_t quantstart;
 
77
  grub_uint8_t freebytes[GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT / 8];
 
78
};
 
79
 
 
80
struct grub_relocator_fw_leftover *leftovers;
 
81
#endif
 
82
 
 
83
struct grub_relocator_extra_block *extra_blocks;
 
84
 
 
85
void *
 
86
get_virtual_current_address (grub_relocator_chunk_t in)
 
87
{
 
88
  return in->srcv;
 
89
}
 
90
 
 
91
grub_phys_addr_t
 
92
get_physical_target_address (grub_relocator_chunk_t in)
 
93
{
 
94
  return in->target;
 
95
}
 
96
 
 
97
struct grub_relocator *
 
98
grub_relocator_new (void)
 
99
{
 
100
  struct grub_relocator *ret;
 
101
 
 
102
  grub_cpu_relocator_init ();
 
103
 
 
104
  ret = grub_zalloc (sizeof (struct grub_relocator));
 
105
  if (!ret)
 
106
    return NULL;
 
107
    
 
108
  ret->postchunks = ~(grub_phys_addr_t) 0;
 
109
  ret->relocators_size = grub_relocator_jumper_size;
 
110
  grub_dprintf ("relocator", "relocators_size=%lu\n",
 
111
                (unsigned long) ret->relocators_size);
 
112
  return ret;
 
113
}
 
114
 
 
115
#define DIGITSORT_BITS 8
 
116
#define DIGITSORT_MASK ((1 << DIGITSORT_BITS) - 1)
 
117
#define BITS_IN_BYTE 8
 
118
 
 
119
#define max(a, b) (((a) > (b)) ? (a) : (b))
 
120
#define min(a, b) (((a) < (b)) ? (a) : (b))
 
121
 
 
122
static inline int
 
123
is_start (int type)
 
124
{
 
125
  return !(type & 1) && (type != COLLISION_START);
 
126
}
 
127
 
 
128
static void
 
129
allocate_regstart (grub_phys_addr_t addr, grub_size_t size, grub_mm_region_t rb,
 
130
                   grub_mm_region_t *regancestor, grub_mm_header_t hancestor)
 
131
{
 
132
  grub_addr_t newreg_start, newreg_raw_start
 
133
    = (grub_addr_t) rb + (addr - grub_vtop (rb)) + size;
 
134
  grub_addr_t newreg_size, newreg_presize;
 
135
  grub_mm_header_t new_header;
 
136
  grub_mm_header_t hb = (grub_mm_header_t) (rb + 1);
 
137
  
 
138
  grub_dprintf ("relocator", "ra = %p, rb = %p\n", regancestor, rb);
 
139
 
 
140
  newreg_start = ALIGN_UP (newreg_raw_start, GRUB_MM_ALIGN);
 
141
  newreg_presize = newreg_start - newreg_raw_start;
 
142
  newreg_size = rb->size - (newreg_start - (grub_addr_t) rb);
 
143
  if ((hb->size << GRUB_MM_ALIGN_LOG2) >= newreg_start
 
144
      - (grub_addr_t) rb)
 
145
    {
 
146
      grub_mm_header_t newhnext = hb->next;
 
147
      grub_size_t newhsize = ((hb->size << GRUB_MM_ALIGN_LOG2)
 
148
                              - (newreg_start
 
149
                                 - (grub_addr_t) rb)) >> GRUB_MM_ALIGN_LOG2;
 
150
      new_header = (void *) (newreg_start + sizeof (*rb));
 
151
      if (newhnext == hb)
 
152
        newhnext = new_header;
 
153
      new_header->next = newhnext;
 
154
      new_header->size = newhsize;
 
155
      new_header->magic = GRUB_MM_FREE_MAGIC;
 
156
    }
 
157
  else
 
158
    {
 
159
      new_header = hb->next;
 
160
      if (new_header == hb)
 
161
        new_header = (void *) (newreg_start + sizeof (*rb));        
 
162
    }
 
163
  {
 
164
    struct grub_mm_header *newregfirst = rb->first;
 
165
    struct grub_mm_region *newregnext = rb->next;
 
166
    struct grub_mm_region *newreg = (void *) newreg_start;
 
167
    hancestor->next = new_header;
 
168
    if (newregfirst == hb)
 
169
      newregfirst = new_header;
 
170
    newreg->first = newregfirst;
 
171
    newreg->next = newregnext;
 
172
    newreg->pre_size = newreg_presize;
 
173
    newreg->size = newreg_size;
 
174
    *regancestor = newreg;
 
175
    {
 
176
      grub_mm_header_t h = newreg->first, hp = NULL;
 
177
      do
 
178
        {
 
179
          if ((void *) h < (void *) (newreg + 1))
 
180
            grub_fatal ("Failed to adjust memory region: %p, %p, %p, %p, %p",
 
181
                        newreg, newreg->first, h, hp, hb);
 
182
          if ((void *) h == (void *) (newreg + 1))
 
183
            grub_dprintf ("relocator",
 
184
                          "Free start memory region: %p, %p, %p, %p, %p",
 
185
                          newreg, newreg->first, h, hp, hb);
 
186
 
 
187
          hp = h;
 
188
          h = h->next;
 
189
        }
 
190
      while (h != newreg->first);
 
191
    }
 
192
  }
 
193
}
 
194
 
 
195
static void
 
196
allocate_inreg (grub_phys_addr_t paddr, grub_size_t size,
 
197
                grub_mm_header_t hb, grub_mm_header_t hbp,
 
198
                grub_mm_region_t rb)
 
199
{
 
200
  struct grub_mm_header *foll = NULL;
 
201
  grub_addr_t vaddr = (grub_addr_t) hb + (paddr - grub_vtop (hb));
 
202
 
 
203
  grub_dprintf ("relocator", "inreg paddr = 0x%lx, size = %lu,"
 
204
                " hb = %p, hbp = %p, rb = %p, vaddr = 0x%lx\n",
 
205
                (unsigned long) paddr, (unsigned long) size, hb, hbp,
 
206
                rb, (unsigned long) vaddr);
 
207
    
 
208
  if (ALIGN_UP (vaddr + size, GRUB_MM_ALIGN) + GRUB_MM_ALIGN
 
209
      <= (grub_addr_t) (hb + hb->size))
 
210
    {
 
211
      foll = (void *) ALIGN_UP (vaddr + size, GRUB_MM_ALIGN);
 
212
      foll->magic = GRUB_MM_FREE_MAGIC;
 
213
      foll->size = hb + hb->size - foll;
 
214
      grub_dprintf ("relocator", "foll = %p, foll->size = %lu\n", foll,
 
215
                    (unsigned long) foll->size);
 
216
    }
 
217
 
 
218
  if (vaddr - (grub_addr_t) hb >= sizeof (*hb))
 
219
    {
 
220
      hb->size = ((vaddr - (grub_addr_t) hb) >> GRUB_MM_ALIGN_LOG2);
 
221
      if (foll)
 
222
        {
 
223
          foll->next = hb;
 
224
          hbp->next = foll;
 
225
          if (rb->first == hb)
 
226
            {
 
227
              rb->first = foll;
 
228
            }
 
229
        }
 
230
    }
 
231
  else
 
232
    {
 
233
      if (foll)
 
234
        {
 
235
          foll->next = hb->next;
 
236
        }
 
237
      else
 
238
        foll = hb->next;
 
239
        
 
240
      hbp->next = foll;
 
241
      if (rb->first == hb)
 
242
        {
 
243
          rb->first = foll;
 
244
        }
 
245
      if (rb->first == hb)
 
246
        {
 
247
          rb->first = (void *) (rb + 1);
 
248
        }
 
249
    }
 
250
}
 
251
 
 
252
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
253
static void
 
254
check_leftover (struct grub_relocator_fw_leftover *lo)
 
255
{
 
256
  unsigned i;
 
257
  for (i = 0; i < sizeof (lo->freebytes); i++)
 
258
    if (lo->freebytes[i] != 0xff)
 
259
      return;
 
260
  grub_relocator_firmware_free_region (lo->quantstart,
 
261
                                       GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
262
  *lo->prev = lo->next;
 
263
  if (lo->next)
 
264
    lo->next->prev = lo->prev;
 
265
}
 
266
#endif
 
267
 
 
268
static void
 
269
free_subchunk (const struct grub_relocator_subchunk *subchu)
 
270
{
 
271
  switch (subchu->type)
 
272
    {
 
273
    case CHUNK_TYPE_REGION_START:
 
274
      {
 
275
        grub_mm_region_t r1, r2, *rp;
 
276
        grub_mm_header_t h;
 
277
        grub_size_t pre_size;
 
278
        r1 = subchu->reg;
 
279
        r2 = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) subchu->reg
 
280
                                          + (grub_vtop (subchu->reg)
 
281
                                             - subchu->start) + subchu->size,
 
282
                                          GRUB_MM_ALIGN);
 
283
        for (rp = &grub_mm_base; *rp && *rp != r2; rp = &((*rp)->next));
 
284
        pre_size = subchu->pre_size;
 
285
 
 
286
        if (*rp)
 
287
          {
 
288
            grub_mm_header_t h2, *hp;
 
289
            r1->first = r2->first;
 
290
            r1->next = r2->next;
 
291
            r1->pre_size = pre_size;
 
292
            r1->size = r2->size + (r2 - r1) * sizeof (*r2);
 
293
            *rp = r1;
 
294
            h = (grub_mm_header_t) (r1 + 1);
 
295
            h->next = r2->first;
 
296
            h->magic = GRUB_MM_FREE_MAGIC;
 
297
            h->size = (r2 - r1 - 1);
 
298
            for (hp = &r2->first, h2 = *hp; h2->next != r2->first;
 
299
                 hp = &(h2->next), h2 = *hp)
 
300
              if (h2 == (grub_mm_header_t) (r2 + 1))
 
301
                break;
 
302
            if (h2 == (grub_mm_header_t) (r2 + 1))
 
303
              {
 
304
                h->size = h2->size + (h2 - h);
 
305
                h->next = h2->next;
 
306
                *hp = h;
 
307
                if (hp == &r2->first)
 
308
                  {
 
309
                    for (h2 = r2->first; h2->next != r2->first; h2 = h2->next);
 
310
                    h2->next = h;
 
311
                  }
 
312
              }
 
313
            else
 
314
              {
 
315
                h2->next = h;
 
316
              }
 
317
          }
 
318
        else
 
319
          {
 
320
            r1->pre_size = pre_size;
 
321
            r1->size = (r2 - r1) * sizeof (*r2);
 
322
            /* Find where to insert this region.
 
323
               Put a smaller one before bigger ones,
 
324
               to prevent fragmentation.  */
 
325
            for (rp = &grub_mm_base; *rp; rp = &((*rp)->next))
 
326
              if ((*rp)->size > r1->size)
 
327
                break;
 
328
            r1->next = *rp;
 
329
            *rp = r1->next;
 
330
            h = (grub_mm_header_t) (r1 + 1);
 
331
            r1->first = h;
 
332
            h->next = h;
 
333
            h->magic = GRUB_MM_FREE_MAGIC;
 
334
            h->size = (r2 - r1 - 1);
 
335
          }
 
336
        for (r2 = grub_mm_base; r2; r2 = r2->next)
 
337
          if ((grub_addr_t) r2 + r2->size == (grub_addr_t) r1)
 
338
            break;
 
339
        if (r2)
 
340
          {
 
341
            grub_mm_header_t hl2, hl, g;
 
342
            g = (grub_mm_header_t) ((grub_addr_t) r2 + r2->size);
 
343
            g->size = (grub_mm_header_t) r1 - g;
 
344
            r2->size += r1->size;
 
345
            for (hl = r2->first; hl->next != r2->first; hl = hl->next);
 
346
            for (hl2 = r1->first; hl2->next != r1->first; hl2 = hl2->next);
 
347
            hl2->next = r2->first;
 
348
            r2->first = r1->first;
 
349
            hl->next = r2->first;
 
350
            *rp = (*rp)->next;
 
351
            grub_free (g + 1);
 
352
          }
 
353
        break;
 
354
      }
 
355
    case CHUNK_TYPE_IN_REGION:
 
356
      {
 
357
        grub_mm_header_t h = (grub_mm_header_t) ALIGN_DOWN ((grub_addr_t) subchu->start,
 
358
                                                            GRUB_MM_ALIGN);
 
359
        h->size
 
360
          = ((subchu->start + subchu->size + GRUB_MM_ALIGN - 1) / GRUB_MM_ALIGN)
 
361
          - (subchu->start / GRUB_MM_ALIGN) - 1;
 
362
        h->next = h;
 
363
        h->magic = GRUB_MM_ALLOC_MAGIC;
 
364
        grub_free (h + 1);
 
365
        break;
 
366
      }
 
367
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
368
    case CHUNK_TYPE_FIRMWARE:
 
369
    case CHUNK_TYPE_LEFTOVER:
 
370
      {
 
371
        grub_addr_t fstart, fend;
 
372
        fstart = ALIGN_UP (subchu->start,
 
373
                           GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
374
        fend = ALIGN_DOWN (subchu->start + subchu->size,
 
375
                           GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
376
        if (fstart < fend)
 
377
          grub_relocator_firmware_free_region (fstart, fend - fstart);
 
378
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
379
        if (subchu->pre)
 
380
          {
 
381
            int off = subchu->start - fstart
 
382
              - GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
 
383
            grub_memset (subchu->pre->freebytes + off / 8 + 1,
 
384
                         0xff, sizeof (subchu->pre->freebytes) - off / 8 - 1);
 
385
            subchu->pre->freebytes[off / 8] |= ~((1 << (off % 8)) - 1);
 
386
            check_leftover (subchu->pre);
 
387
          }
 
388
        if (subchu->post)
 
389
          {
 
390
            int off = subchu->start + subchu->size - fend;
 
391
            grub_memset (subchu->pre->freebytes,
 
392
                         0xff, sizeof (subchu->pre->freebytes) - off / 8);
 
393
            subchu->pre->freebytes[off / 8] |= ((1 << (8 - (off % 8))) - 1);
 
394
            check_leftover (subchu->post);
 
395
          }
 
396
#endif
 
397
        *subchu->extra->prev = subchu->extra->next;
 
398
        grub_free (subchu->extra);
 
399
      }
 
400
      break;
 
401
#endif
 
402
    }  
 
403
}
 
404
 
 
405
static int
 
406
malloc_in_range (struct grub_relocator *rel,
 
407
                 grub_addr_t start, grub_addr_t end, grub_addr_t align,
 
408
                 grub_size_t size, struct grub_relocator_chunk *res,
 
409
                 int from_low_priv, int collisioncheck)
 
410
{
 
411
  grub_mm_region_t r, *ra, base_saved;
 
412
  struct grub_relocator_mmap_event *events = NULL, *eventt = NULL, *t;
 
413
  /* 128 is just in case of additional malloc (shouldn't happen).  */
 
414
  unsigned maxevents = 2 + 128;
 
415
  grub_mm_header_t p, pa;
 
416
  unsigned *counter;
 
417
  int nallocs = 0;
 
418
  unsigned j, N = 0;
 
419
  grub_addr_t target = 0;
 
420
 
 
421
  grub_dprintf ("relocator",
 
422
                "trying to allocate in 0x%lx-0x%lx aligned 0x%lx size 0x%lx\n",
 
423
                (unsigned long) start, (unsigned long) end,
 
424
                (unsigned long) align, (unsigned long) size);
 
425
 
 
426
  start = ALIGN_UP (start, align);
 
427
  end = ALIGN_DOWN (end - size, align) + size;
 
428
 
 
429
  if (end < start + size)
 
430
    return 0;
 
431
 
 
432
  /* We have to avoid any allocations when filling scanline events. 
 
433
     Hence 2-stages.
 
434
   */
 
435
  for (r = grub_mm_base; r; r = r->next)
 
436
    {
 
437
      p = r->first;
 
438
      do
 
439
        {
 
440
          if ((grub_addr_t) p < (grub_addr_t) (r + 1)
 
441
              || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
 
442
            grub_fatal ("%d: out of range pointer: %p\n", __LINE__, p);
 
443
          maxevents += 2;
 
444
          p = p->next;
 
445
        }
 
446
      while (p != r->first);
 
447
      maxevents += 4;
 
448
    }
 
449
 
 
450
  if (collisioncheck && rel)
 
451
    {
 
452
      struct grub_relocator_chunk *chunk;
 
453
      for (chunk = rel->chunks; chunk; chunk = chunk->next)
 
454
        maxevents += 2;
 
455
    }
 
456
 
 
457
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
458
  {
 
459
    struct grub_relocator_extra_block *cur;
 
460
    for (cur = extra_blocks; cur; cur = cur->next)
 
461
      maxevents += 2;
 
462
  }
 
463
  for (r = grub_mm_base; r; r = r->next)
 
464
    maxevents += 2;
 
465
 
 
466
  maxevents += grub_relocator_firmware_get_max_events ();
 
467
#endif
 
468
 
 
469
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
470
  {
 
471
    struct grub_relocator_fw_leftover *cur;
 
472
    for (cur = leftovers; cur; cur = cur->next)
 
473
      {
 
474
        int l = 0;
 
475
        unsigned i;
 
476
        for (i = 0; i < GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT; i++)
 
477
          {
 
478
            if (l != ((cur->freebytes[i / 8] >> (i % 8)) & 1))
 
479
              maxevents++;
 
480
            l = ((cur->freebytes[i / 8] >> (i % 8)) & 1);
 
481
          }
 
482
        if (l)
 
483
          maxevents++;
 
484
      }
 
485
  }
 
486
#endif
 
487
 
 
488
  events = grub_malloc (maxevents * sizeof (events[0]));
 
489
  eventt = grub_malloc (maxevents * sizeof (events[0]));
 
490
  counter = grub_malloc ((DIGITSORT_MASK + 2) * sizeof (counter[0]));
 
491
  if (!events || !eventt || !counter)
 
492
    {
 
493
      grub_dprintf ("relocator", "events or counter allocation failed %d\n",
 
494
                    maxevents);
 
495
      grub_free (events);
 
496
      grub_free (eventt);
 
497
      grub_free (counter);
 
498
      return 0;
 
499
    }
 
500
 
 
501
  if (collisioncheck && rel)
 
502
    {
 
503
      struct grub_relocator_chunk *chunk;
 
504
      for (chunk = rel->chunks; chunk; chunk = chunk->next)
 
505
        {
 
506
          events[N].type = COLLISION_START;
 
507
          events[N].pos = chunk->target;
 
508
          N++;
 
509
          events[N].type = COLLISION_END;
 
510
          events[N].pos = chunk->target + chunk->size;
 
511
          N++;
 
512
        }
 
513
    }
 
514
 
 
515
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
516
  for (r = grub_mm_base; r; r = r->next)
 
517
    {
 
518
      grub_dprintf ("relocator", "Blocking at 0x%lx-0x%lx\n",
 
519
                    (unsigned long) r - r->pre_size, 
 
520
                    (unsigned long) (r + 1) + r->size);
 
521
      events[N].type = FIRMWARE_BLOCK_START;
 
522
      events[N].pos = (grub_addr_t) r - r->pre_size;
 
523
      N++;
 
524
      events[N].type = FIRMWARE_BLOCK_END;
 
525
      events[N].pos = (grub_addr_t) (r + 1) + r->size;
 
526
      N++;
 
527
    }
 
528
  {
 
529
    struct grub_relocator_extra_block *cur;
 
530
    for (cur = extra_blocks; cur; cur = cur->next)
 
531
      {
 
532
        grub_dprintf ("relocator", "Blocking at 0x%lx-0x%lx\n",
 
533
                      (unsigned long) cur->start, (unsigned long) cur->end);
 
534
        events[N].type = FIRMWARE_BLOCK_START;
 
535
        events[N].pos = cur->start;
 
536
        N++;
 
537
        events[N].type = FIRMWARE_BLOCK_END;
 
538
        events[N].pos = cur->end;
 
539
        N++;
 
540
      }
 
541
  }
 
542
 
 
543
  N += grub_relocator_firmware_fill_events (events + N);
 
544
 
 
545
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
546
  {
 
547
    struct grub_relocator_fw_leftover *cur;
 
548
    for (cur = leftovers; cur; cur = cur->next)
 
549
      {
 
550
        unsigned i;
 
551
        int l = 0;
 
552
        for (i = 0; i < GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT; i++)
 
553
          {
 
554
            if (l != ((cur->freebytes[i / 8] >> (i % 8)) & 1))
 
555
              {
 
556
                events[N].type = l ? REG_LEFTOVER_END : REG_LEFTOVER_START;
 
557
                events[N].pos = cur->quantstart + i;
 
558
                events[N].leftover = cur;
 
559
                N++;
 
560
              }
 
561
            l = ((cur->freebytes[i / 8] >> (i % 8)) & 1);
 
562
          }
 
563
        if (l)
 
564
          {
 
565
            events[N].type = REG_LEFTOVER_END;
 
566
            events[N].pos = cur->quantstart + i;
 
567
            events[N].leftover = cur;
 
568
            N++;
 
569
          }
 
570
      }
 
571
  }
 
572
#endif
 
573
#endif
 
574
 
 
575
  /* No malloc from this point.  */
 
576
  base_saved = grub_mm_base;
 
577
  grub_mm_base = NULL;
 
578
 
 
579
  for (ra = &base_saved, r = *ra; r; ra = &(r->next), r = *ra)
 
580
    {
 
581
      pa = r->first;
 
582
      p = pa->next;
 
583
      if (p->magic == GRUB_MM_ALLOC_MAGIC)
 
584
        continue;
 
585
      do 
 
586
        {
 
587
          if (p->magic != GRUB_MM_FREE_MAGIC)
 
588
            grub_fatal (__FILE__":%d free magic broken at %p (0x%x)\n",
 
589
                        __LINE__, p, p->magic);
 
590
          if (p == (grub_mm_header_t) (r + 1))
 
591
            {
 
592
              events[N].type = REG_BEG_START;
 
593
              events[N].pos = grub_vtop (r) - r->pre_size;
 
594
              events[N].reg = r;
 
595
              events[N].regancestor = ra;
 
596
              events[N].head = p;
 
597
              events[N].hancestor = pa;
 
598
              N++;
 
599
              events[N].type = REG_BEG_END;
 
600
              events[N].pos = grub_vtop (p + p->size) - sizeof (*r)
 
601
                - sizeof (struct grub_mm_header);
 
602
              N++;
 
603
            }
 
604
          else
 
605
            {
 
606
              events[N].type = IN_REG_START;
 
607
              events[N].pos = grub_vtop (p);
 
608
              events[N].head = p;
 
609
              events[N].hancestor = pa;
 
610
              events[N].reg = r;
 
611
              N++;
 
612
              events[N].type = IN_REG_END;
 
613
              events[N].pos = grub_vtop (p + p->size);
 
614
              N++;
 
615
            }
 
616
          pa = p;
 
617
          p = pa->next;
 
618
        }
 
619
      while (pa != r->first);
 
620
    }
 
621
 
 
622
  /* Put ending events after starting events.  */
 
623
  {
 
624
    int st = 0, e = N / 2;
 
625
    for (j = 0; j < N; j++)
 
626
      if (is_start (events[j].type) || events[j].type == COLLISION_START)
 
627
        eventt[st++] = events[j];
 
628
      else
 
629
        eventt[e++] = events[j];
 
630
    t = eventt;
 
631
    eventt = events;
 
632
    events = t;
 
633
  }
 
634
 
 
635
  {
 
636
    unsigned i;
 
637
    for (i = 0; i < (BITS_IN_BYTE * sizeof (grub_addr_t) / DIGITSORT_BITS);
 
638
         i++)
 
639
      {
 
640
        memset (counter, 0, (1 + (1 << DIGITSORT_BITS)) * sizeof (counter[0]));
 
641
        for (j = 0; j < N; j++)
 
642
          counter[((events[j].pos >> (DIGITSORT_BITS * i)) 
 
643
                   & DIGITSORT_MASK) + 1]++;
 
644
        for (j = 0; j <= DIGITSORT_MASK; j++)
 
645
          counter[j+1] += counter[j];
 
646
        for (j = 0; j < N; j++)
 
647
          eventt[counter[((events[j].pos >> (DIGITSORT_BITS * i)) 
 
648
                          & DIGITSORT_MASK)]++] = events[j];
 
649
        t = eventt;
 
650
        eventt = events;
 
651
        events = t;
 
652
      }
 
653
  }
 
654
 
 
655
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
656
 retry:
 
657
#endif
 
658
 
 
659
  /* Now events are nicely sorted.  */
 
660
  {
 
661
    int nstarted = 0, ncollisions = 0, nstartedfw = 0, nblockfw = 0;
 
662
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
663
    int nlefto = 0;
 
664
#else
 
665
    const int nlefto = 0;
 
666
#endif
 
667
    grub_addr_t starta = 0;
 
668
    for (j = from_low_priv ? 0 : N - 1; from_low_priv ? j < N : (j + 1); 
 
669
         from_low_priv ? j++ : j--)
 
670
      {
 
671
        int isinsidebefore, isinsideafter;
 
672
        isinsidebefore = (!ncollisions && (nstarted || (((nlefto || nstartedfw)
 
673
                                                         && !nblockfw))));
 
674
        switch (events[j].type)
 
675
          {
 
676
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
677
          case REG_FIRMWARE_START:
 
678
            nstartedfw++;
 
679
            break;
 
680
 
 
681
          case REG_FIRMWARE_END:
 
682
            nstartedfw--;
 
683
            break;
 
684
 
 
685
          case FIRMWARE_BLOCK_START:
 
686
            nblockfw++;
 
687
            break;
 
688
 
 
689
          case FIRMWARE_BLOCK_END:
 
690
            nblockfw--;
 
691
            break;
 
692
#endif
 
693
 
 
694
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
695
          case REG_LEFTOVER_START:
 
696
            nlefto++;
 
697
            break;
 
698
 
 
699
          case REG_LEFTOVER_END:
 
700
            nlefto--;
 
701
            break;
 
702
#endif
 
703
 
 
704
          case COLLISION_START:
 
705
            ncollisions++;
 
706
            break;
 
707
 
 
708
          case COLLISION_END:
 
709
            ncollisions--;
 
710
            break;
 
711
 
 
712
          case IN_REG_START:
 
713
          case REG_BEG_START:
 
714
            nstarted++;
 
715
            break;
 
716
 
 
717
          case IN_REG_END:
 
718
          case REG_BEG_END:
 
719
            nstarted--;
 
720
            break;
 
721
          }
 
722
        isinsideafter = (!ncollisions && (nstarted || ((nlefto || nstartedfw) 
 
723
                                                       && !nblockfw)));
 
724
        if (!isinsidebefore && isinsideafter)
 
725
          starta = from_low_priv ? ALIGN_UP (events[j].pos, align)
 
726
            : ALIGN_DOWN (events[j].pos - size, align) + size;
 
727
        if (isinsidebefore && !isinsideafter && from_low_priv)
 
728
          {
 
729
            target = starta;
 
730
            if (target < start)
 
731
              target = start;
 
732
            if (target + size <= end && target + size <= events[j].pos)
 
733
              /* Found an usable address.  */
 
734
              goto found;
 
735
          }
 
736
        if (isinsidebefore && !isinsideafter && !from_low_priv)
 
737
          {
 
738
            target = starta - size;
 
739
            if (target > end - size)
 
740
              target = end - size;
 
741
            if (target >= start && target >= events[j].pos)
 
742
              goto found;
 
743
          }
 
744
      }
 
745
  }
 
746
 
 
747
  grub_mm_base = base_saved;
 
748
  grub_free (events);
 
749
  grub_free (eventt);
 
750
  grub_free (counter);
 
751
  return 0;
 
752
 
 
753
 found:
 
754
  {
 
755
    int inreg = 0, regbeg = 0, ncol = 0;
 
756
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
757
    int fwin = 0, fwb = 0, fwlefto = 0;
 
758
#endif
 
759
    int last_start = 0;
 
760
    for (j = 0; j < N; j++)
 
761
      {
 
762
        int typepre;
 
763
        if (ncol)
 
764
          typepre = -1;
 
765
        else if (regbeg)
 
766
          typepre = CHUNK_TYPE_REGION_START;
 
767
        else if (inreg)
 
768
          typepre = CHUNK_TYPE_IN_REGION;
 
769
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
770
        else if (fwin && !fwb)
 
771
          typepre = CHUNK_TYPE_FIRMWARE;
 
772
        else if (fwlefto && !fwb)
 
773
          typepre = CHUNK_TYPE_LEFTOVER;
 
774
#endif
 
775
        else
 
776
          typepre = -1;
 
777
 
 
778
        if (j != 0 && events[j - 1].pos != events[j].pos)
 
779
          {
 
780
            grub_addr_t alloc_start, alloc_end;
 
781
            alloc_start = max (events[j - 1].pos, target);
 
782
            alloc_end = min (events[j].pos, target + size);
 
783
            if (alloc_end > alloc_start)
 
784
              {
 
785
                switch (typepre)
 
786
                  {
 
787
                  case CHUNK_TYPE_REGION_START:
 
788
                    allocate_regstart (alloc_start, alloc_end - alloc_start,
 
789
                                       events[last_start].reg,
 
790
                                       events[last_start].regancestor,
 
791
                                       events[last_start].hancestor);
 
792
                    /* TODO: maintain a reverse lookup tree for hancestor.  */
 
793
                    {
 
794
                      unsigned k;
 
795
                      for (k = 0; k < N; k++)
 
796
                        if (events[k].hancestor == events[last_start].head)
 
797
                          events[k].hancestor = events[last_start].hancestor;
 
798
                    }
 
799
                    break;
 
800
                  case CHUNK_TYPE_IN_REGION:
 
801
                    allocate_inreg (alloc_start, alloc_end - alloc_start,
 
802
                                    events[last_start].head,
 
803
                                    events[last_start].hancestor,
 
804
                                    events[last_start].reg);
 
805
                    {
 
806
                      unsigned k;
 
807
                      for (k = 0; k < N; k++)
 
808
                        if (events[k].hancestor == events[last_start].head)
 
809
                          events[k].hancestor = events[last_start].hancestor;
 
810
                    }
 
811
                    break;
 
812
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
813
                  case CHUNK_TYPE_FIRMWARE:
 
814
                    {
 
815
                      grub_addr_t fstart, fend;
 
816
                      fstart
 
817
                        = ALIGN_DOWN (alloc_start,
 
818
                                      GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
819
                      fend
 
820
                        = ALIGN_UP (alloc_end,
 
821
                                    GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
822
                      grub_dprintf ("relocator", "requesting %lx-%lx\n",
 
823
                                    (unsigned long) fstart,
 
824
                                    (unsigned long) fend);
 
825
                      /* The failure here can be very expensive.  */
 
826
                      if (!grub_relocator_firmware_alloc_region (fstart, 
 
827
                                                                 fend - fstart))
 
828
                        {
 
829
                          if (from_low_priv)
 
830
                            start = fend;
 
831
                          else
 
832
                            end = fstart;
 
833
                          goto retry;
 
834
                        }
 
835
                      break;
 
836
                    }
 
837
#endif
 
838
 
 
839
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
840
                  case CHUNK_TYPE_LEFTOVER:
 
841
                    {
 
842
                      unsigned offstart = alloc_start
 
843
                        % GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
 
844
                      unsigned offend = alloc_end
 
845
                        % GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
 
846
                      struct grub_relocator_fw_leftover *lo
 
847
                        = events[last_start].leftover;
 
848
                      lo->freebytes[offstart / 8]
 
849
                        &= ((1 << (8 - (start % 8))) - 1);
 
850
                      grub_memset (lo->freebytes + (offstart + 7) / 8, 0,
 
851
                                   offend / 8 - (offstart + 7) / 8);
 
852
                      lo->freebytes[offend / 8] &= ~((1 << (offend % 8)) - 1);
 
853
                    }
 
854
                    break;
 
855
#endif
 
856
                  }
 
857
                nallocs++;
 
858
              }
 
859
          }
 
860
          
 
861
        switch (events[j].type)
 
862
          {
 
863
          case REG_BEG_START:
 
864
          case IN_REG_START:
 
865
            if (events[j].type == REG_BEG_START &&
 
866
                (grub_addr_t) (events[j].reg + 1) > target)
 
867
              regbeg++;
 
868
            else
 
869
              inreg++;
 
870
            last_start = j;
 
871
            break;
 
872
 
 
873
          case REG_BEG_END:
 
874
          case IN_REG_END:
 
875
            if (regbeg)
 
876
              regbeg--;
 
877
            else
 
878
              inreg--;
 
879
            break;
 
880
 
 
881
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
882
          case REG_FIRMWARE_START:
 
883
            fwin++;
 
884
            break;
 
885
 
 
886
          case REG_FIRMWARE_END:
 
887
            fwin--;
 
888
            break;
 
889
 
 
890
          case FIRMWARE_BLOCK_START:
 
891
            fwb++;
 
892
            break;
 
893
 
 
894
          case FIRMWARE_BLOCK_END:
 
895
            fwb--;
 
896
            break;
 
897
#endif
 
898
 
 
899
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
900
          case REG_LEFTOVER_START:
 
901
            fwlefto++;
 
902
            break;
 
903
 
 
904
          case REG_LEFTOVER_END:
 
905
            fwlefto--;
 
906
            break;
 
907
#endif
 
908
          case COLLISION_START:
 
909
            ncol++;
 
910
            break;
 
911
          case COLLISION_END:
 
912
            ncol--;
 
913
            break;
 
914
          }
 
915
 
 
916
      }
 
917
  }
 
918
 
 
919
  /* Malloc is available again.  */
 
920
  grub_mm_base = base_saved;
 
921
 
 
922
  {
 
923
    int last_start = 0;
 
924
    int inreg = 0, regbeg = 0, ncol = 0;
 
925
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
926
    int fwin = 0, fwlefto = 0, fwb = 0;
 
927
#endif
 
928
    unsigned cural = 0;
 
929
    int oom = 0;
 
930
    res->subchunks = grub_malloc (sizeof (res->subchunks[0]) * nallocs);
 
931
    if (!res->subchunks)
 
932
      oom = 1;
 
933
    res->nsubchunks = nallocs;
 
934
 
 
935
    for (j = 0; j < N; j++)
 
936
      {
 
937
        int typepre;
 
938
        if (ncol)
 
939
          typepre = -1;
 
940
        else if (regbeg)
 
941
          typepre = CHUNK_TYPE_REGION_START;
 
942
        else if (inreg)
 
943
          typepre = CHUNK_TYPE_IN_REGION;
 
944
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
945
        else if (fwin && !fwb)
 
946
          typepre = CHUNK_TYPE_FIRMWARE;
 
947
        else if (fwlefto && !fwb)
 
948
          typepre = CHUNK_TYPE_LEFTOVER;
 
949
#endif
 
950
        else
 
951
          typepre = -1;
 
952
 
 
953
        if (j != 0 && events[j - 1].pos != events[j].pos)
 
954
          {
 
955
            grub_addr_t alloc_start, alloc_end;
 
956
            struct grub_relocator_subchunk tofree;
 
957
            struct grub_relocator_subchunk *curschu = &tofree;
 
958
            if (!oom)
 
959
              curschu = &res->subchunks[cural];
 
960
            alloc_start = max (events[j - 1].pos, target);
 
961
            alloc_end = min (events[j].pos, target + size);
 
962
            if (alloc_end > alloc_start)
 
963
              {
 
964
                grub_dprintf ("relocator", "subchunk 0x%lx-0x%lx, %d\n",
 
965
                              (unsigned long) alloc_start,
 
966
                              (unsigned long) alloc_end, typepre);
 
967
                curschu->type = typepre;
 
968
                curschu->start = alloc_start;
 
969
                curschu->size = alloc_end - alloc_start;
 
970
                if (typepre == CHUNK_TYPE_REGION_START
 
971
                    || typepre == CHUNK_TYPE_IN_REGION)
 
972
                  {
 
973
                    curschu->reg = events[last_start].reg;
 
974
                    curschu->pre_size = alloc_start - events[j - 1].pos;
 
975
                  }
 
976
                if (!oom && (typepre == CHUNK_TYPE_REGION_START
 
977
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
978
                             || typepre == CHUNK_TYPE_FIRMWARE
 
979
#endif
 
980
                             ))
 
981
                  {
 
982
                    struct grub_relocator_extra_block *ne;
 
983
                    ne = grub_malloc (sizeof (*ne));
 
984
                    if (!ne)
 
985
                      {
 
986
                        oom = 1;
 
987
                        grub_memcpy (&tofree, curschu, sizeof (tofree));
 
988
                      }
 
989
                    else
 
990
                      {
 
991
                        ne->start = alloc_start;
 
992
                        ne->end = alloc_end;
 
993
                        ne->next = extra_blocks;
 
994
                        ne->prev = &extra_blocks;
 
995
                        if (extra_blocks)
 
996
                          extra_blocks->prev = &(ne->next);
 
997
                        extra_blocks = ne;
 
998
                        curschu->extra = ne;
 
999
                      }
 
1000
                  }
 
1001
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
1002
                if (!oom && typepre == CHUNK_TYPE_FIRMWARE)
 
1003
                  {
 
1004
                    grub_addr_t fstart, fend;
 
1005
 
 
1006
                    fstart
 
1007
                      = ALIGN_DOWN (alloc_start,
 
1008
                                    GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
1009
                    fend
 
1010
                      = ALIGN_UP (alloc_end,
 
1011
                                  GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT);
 
1012
 
 
1013
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
1014
                    {
 
1015
                      struct grub_relocator_fw_leftover *lo1 = NULL;
 
1016
                      struct grub_relocator_fw_leftover *lo2 = NULL;
 
1017
                      if (fstart != alloc_start)
 
1018
                        lo1 = grub_malloc (sizeof (*lo1));
 
1019
                      if (fend != alloc_end)
 
1020
                        lo2 = grub_malloc (sizeof (*lo2));
 
1021
                      if ((!lo1 && fstart != alloc_start)
 
1022
                          || (!lo2 && fend != alloc_end))
 
1023
                        {
 
1024
                          struct grub_relocator_extra_block *ne;
 
1025
                          grub_free (lo1);
 
1026
                          grub_free (lo2);
 
1027
                          lo1 = NULL;
 
1028
                          lo2 = NULL;
 
1029
                          oom = 1;
 
1030
                          grub_memcpy (&tofree, curschu, sizeof (tofree));
 
1031
                          ne = extra_blocks;
 
1032
                          extra_blocks = extra_blocks->next;
 
1033
                          grub_free (ne);
 
1034
                        }
 
1035
                      if (lo1)
 
1036
                        {
 
1037
                          lo1->quantstart = fstart;
 
1038
                          grub_memset (lo1->freebytes, 0xff,
 
1039
                                       (alloc_start - fstart) / 8);
 
1040
                          lo1->freebytes[(alloc_start - fstart) / 8]
 
1041
                            = (1 << ((alloc_start - fstart) % 8)) - 1;
 
1042
                          grub_memset (lo1->freebytes
 
1043
                                       + ((alloc_start - fstart) / 8) + 1, 0,
 
1044
                                       sizeof (lo1->freebytes)
 
1045
                                       - (alloc_start - fstart) / 8 - 1);
 
1046
                          lo1->next = leftovers;
 
1047
                          lo1->prev = &leftovers;
 
1048
                          if (leftovers)
 
1049
                            leftovers->prev = &lo1->next;
 
1050
                          leftovers = lo1;
 
1051
                        }
 
1052
                      if (lo2)
 
1053
                        {
 
1054
                          lo2->quantstart
 
1055
                            = fend - GRUB_RELOCATOR_FIRMWARE_REQUESTS_QUANT;
 
1056
                          grub_memset (lo2->freebytes, 0,
 
1057
                                       (alloc_end - lo2->quantstart) / 8);
 
1058
                          lo2->freebytes[(alloc_end - lo2->quantstart) / 8]
 
1059
                            = ~((1 << ((alloc_end - lo2->quantstart) % 8)) - 1);
 
1060
                          grub_memset (lo2->freebytes
 
1061
                                       + ((alloc_end - lo2->quantstart) / 8)
 
1062
                                       + 1, 0, sizeof (lo2->freebytes)
 
1063
                                       - (alloc_end - lo2->quantstart) / 8 - 1);
 
1064
                          lo2->prev = &leftovers;
 
1065
                          if (leftovers)
 
1066
                            leftovers->prev = &lo2->next;
 
1067
                          lo2->next = leftovers;
 
1068
                          leftovers = lo2;
 
1069
                        }
 
1070
                      curschu->pre = lo1;
 
1071
                      curschu->post = lo2;
 
1072
                    }
 
1073
#endif
 
1074
                  }
 
1075
 
 
1076
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
1077
                if (typepre == CHUNK_TYPE_LEFTOVER)
 
1078
                  {
 
1079
                    curschu->pre = events[last_start].leftover;
 
1080
                    curschu->post = events[last_start].leftover;
 
1081
                  }
 
1082
#endif
 
1083
 
 
1084
#endif
 
1085
                if (!oom)
 
1086
                  cural++;
 
1087
                else
 
1088
                  free_subchunk (&tofree);
 
1089
              }
 
1090
          }
 
1091
 
 
1092
        switch (events[j].type)
 
1093
          {
 
1094
          case REG_BEG_START:
 
1095
          case IN_REG_START:
 
1096
            if (events[j].type == REG_BEG_START &&
 
1097
                (grub_addr_t) (events[j].reg + 1) > target)
 
1098
              regbeg++;
 
1099
            else
 
1100
              inreg++;
 
1101
            last_start = j;
 
1102
            break;
 
1103
 
 
1104
          case REG_BEG_END:
 
1105
          case IN_REG_END:
 
1106
            inreg = regbeg = 0;
 
1107
            break;
 
1108
 
 
1109
#if GRUB_RELOCATOR_HAVE_FIRMWARE_REQUESTS
 
1110
          case REG_FIRMWARE_START:
 
1111
            fwin++;
 
1112
            break;
 
1113
 
 
1114
          case REG_FIRMWARE_END:
 
1115
            fwin--;
 
1116
            break;
 
1117
 
 
1118
          case FIRMWARE_BLOCK_START:
 
1119
            fwb++;
 
1120
            break;
 
1121
 
 
1122
          case FIRMWARE_BLOCK_END:
 
1123
            fwb--;
 
1124
            break;
 
1125
#endif
 
1126
 
 
1127
#if GRUB_RELOCATOR_HAVE_LEFTOVERS
 
1128
          case REG_LEFTOVER_START:
 
1129
            fwlefto++;
 
1130
            break;
 
1131
 
 
1132
          case REG_LEFTOVER_END:
 
1133
            fwlefto--;
 
1134
            break;
 
1135
#endif
 
1136
          case COLLISION_START:
 
1137
            ncol++;
 
1138
            break;
 
1139
          case COLLISION_END:
 
1140
            ncol--;
 
1141
            break;
 
1142
          }
 
1143
      }
 
1144
    if (oom)
 
1145
      {
 
1146
        unsigned i;
 
1147
        for (i = 0; i < cural; i++)
 
1148
          free_subchunk (&res->subchunks[i]);
 
1149
        grub_free (res->subchunks);
 
1150
        grub_dprintf ("relocator", "allocation failed with out-of-memory\n");
 
1151
        return 0;
 
1152
      }
 
1153
  }
 
1154
 
 
1155
  res->src = target;
 
1156
  res->size = size;
 
1157
  grub_dprintf ("relocator", "allocated: 0x%lx+0x%lx\n", (unsigned long) target,
 
1158
                (unsigned long) size);
 
1159
 
 
1160
  return 1;
 
1161
}
 
1162
 
 
1163
static void
 
1164
adjust_limits (struct grub_relocator *rel, 
 
1165
               grub_phys_addr_t *min_addr, grub_phys_addr_t *max_addr,
 
1166
               grub_phys_addr_t in_min, grub_phys_addr_t in_max)
 
1167
{
 
1168
  struct grub_relocator_chunk *chunk;
 
1169
 
 
1170
  *min_addr = 0;
 
1171
  *max_addr = rel->postchunks;
 
1172
 
 
1173
  /* Keep chunks in memory in the same order as they'll be after relocation.  */
 
1174
  for (chunk = rel->chunks; chunk; chunk = chunk->next)
 
1175
    {
 
1176
      if (chunk->target > in_max && chunk->src < *max_addr
 
1177
          && chunk->src < rel->postchunks)
 
1178
        *max_addr = chunk->src;
 
1179
      if (chunk->target + chunk->size <= in_min
 
1180
          && chunk->src + chunk->size > *min_addr
 
1181
          && chunk->src < rel->postchunks)
 
1182
        *min_addr = chunk->src + chunk->size;
 
1183
    }
 
1184
}
 
1185
 
 
1186
grub_err_t
 
1187
grub_relocator_alloc_chunk_addr (struct grub_relocator *rel,
 
1188
                                 grub_relocator_chunk_t *out,
 
1189
                                 grub_phys_addr_t target, grub_size_t size)
 
1190
{
 
1191
  struct grub_relocator_chunk *chunk;
 
1192
  grub_phys_addr_t min_addr = 0, max_addr;
 
1193
 
 
1194
  if (target > ~size)
 
1195
    return grub_error (GRUB_ERR_OUT_OF_RANGE, "address is out of range");
 
1196
 
 
1197
  adjust_limits (rel, &min_addr, &max_addr, target, target);
 
1198
 
 
1199
  for (chunk = rel->chunks; chunk; chunk = chunk->next)
 
1200
    if ((chunk->target <= target && target < chunk->target + chunk->size)
 
1201
        || (target <= chunk->target && chunk->target < target + size))
 
1202
      return grub_error (GRUB_ERR_BAD_ARGUMENT, "overlap detected");
 
1203
 
 
1204
  chunk = grub_malloc (sizeof (struct grub_relocator_chunk));
 
1205
  if (!chunk)
 
1206
    return grub_errno;
 
1207
 
 
1208
  grub_dprintf ("relocator",
 
1209
                "min_addr = 0x%llx, max_addr = 0x%llx, target = 0x%llx\n",
 
1210
                (unsigned long long) min_addr, (unsigned long long) max_addr,
 
1211
                (unsigned long long) target);
 
1212
 
 
1213
  do
 
1214
    {
 
1215
      /* A trick to improve Linux allocation.  */
 
1216
#if defined (__i386__) || defined (__x86_64__)
 
1217
      if (target < 0x100000)
 
1218
        if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
 
1219
                             size, chunk, 0, 1))
 
1220
          {
 
1221
            if (rel->postchunks > chunk->src)
 
1222
              rel->postchunks = chunk->src;
 
1223
            break;
 
1224
          }
 
1225
#endif
 
1226
      if (malloc_in_range (rel, target, max_addr, 1, size, chunk, 1, 0))
 
1227
        break;
 
1228
 
 
1229
      if (malloc_in_range (rel, min_addr, target, 1, size, chunk, 0, 0))
 
1230
        break;
 
1231
 
 
1232
      if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
 
1233
                           size, chunk, 0, 1))
 
1234
        {
 
1235
          if (rel->postchunks > chunk->src)
 
1236
            rel->postchunks = chunk->src;
 
1237
          break;
 
1238
        }
 
1239
 
 
1240
      grub_dprintf ("relocator", "not allocated\n");
 
1241
      grub_free (chunk);
 
1242
      return grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
 
1243
    }
 
1244
  while (0);
 
1245
 
 
1246
  grub_dprintf ("relocator", "allocated 0x%llx/0x%llx\n",
 
1247
                (unsigned long long) chunk->src, (unsigned long long) target);
 
1248
 
 
1249
  if (rel->highestaddr < target + size)
 
1250
    rel->highestaddr = target + size;
 
1251
 
 
1252
  if (rel->highestaddr < chunk->src + size)
 
1253
    rel->highestaddr = chunk->src + size;
 
1254
 
 
1255
  if (chunk->src < rel->postchunks)
 
1256
    {
 
1257
      if (rel->highestnonpostaddr < target + size)
 
1258
        rel->highestnonpostaddr = target + size;
 
1259
      
 
1260
      if (rel->highestnonpostaddr < chunk->src + size)
 
1261
        rel->highestnonpostaddr = chunk->src + size;  
 
1262
    }
 
1263
 
 
1264
  grub_dprintf ("relocator", "relocators_size=%ld\n",
 
1265
                (unsigned long) rel->relocators_size);
 
1266
 
 
1267
  if (chunk->src < target)
 
1268
    rel->relocators_size += grub_relocator_backward_size;
 
1269
  if (chunk->src > target)
 
1270
    rel->relocators_size += grub_relocator_forward_size;
 
1271
 
 
1272
  grub_dprintf ("relocator", "relocators_size=%ld\n",
 
1273
                (unsigned long) rel->relocators_size);
 
1274
 
 
1275
  chunk->target = target;
 
1276
  chunk->size = size;
 
1277
  chunk->next = rel->chunks;
 
1278
  rel->chunks = chunk;
 
1279
  grub_dprintf ("relocator", "cur = %p, next = %p\n", rel->chunks,
 
1280
                rel->chunks->next);
 
1281
 
 
1282
  chunk->srcv = grub_map_memory (chunk->src, chunk->size);
 
1283
  *out = chunk;
 
1284
#ifdef DEBUG_RELOCATOR
 
1285
  {
 
1286
    grub_mm_region_t r;
 
1287
    grub_mm_header_t p;
 
1288
    grub_memset (chunk->srcv, 0xfa, chunk->size);
 
1289
    for (r = grub_mm_base; r; r = r->next)
 
1290
      {
 
1291
        p = r->first;
 
1292
        do
 
1293
          {
 
1294
            if ((grub_addr_t) p < (grub_addr_t) (r + 1)
 
1295
                || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
 
1296
              grub_fatal (__FILE__ ":%d: out of range pointer: %p\n", __LINE__, p);
 
1297
            p = p->next;
 
1298
          }
 
1299
        while (p != r->first);
 
1300
      }
 
1301
  }
 
1302
#endif
 
1303
  return GRUB_ERR_NONE;
 
1304
}
 
1305
 
 
1306
grub_err_t
 
1307
grub_relocator_alloc_chunk_align (struct grub_relocator *rel,
 
1308
                                  grub_relocator_chunk_t *out,
 
1309
                                  grub_phys_addr_t min_addr,
 
1310
                                  grub_phys_addr_t max_addr,
 
1311
                                  grub_size_t size, grub_size_t align,
 
1312
                                  int preference)
 
1313
{
 
1314
  grub_addr_t min_addr2 = 0, max_addr2;
 
1315
  struct grub_relocator_chunk *chunk;
 
1316
 
 
1317
  if (max_addr > ~size)
 
1318
    max_addr = ~size;
 
1319
 
 
1320
#ifdef GRUB_MACHINE_PCBIOS
 
1321
  if (min_addr < 0x1000)
 
1322
    min_addr = 0x1000;
 
1323
#endif
 
1324
 
 
1325
  grub_dprintf ("relocator", "chunks = %p\n", rel->chunks);
 
1326
 
 
1327
  chunk = grub_malloc (sizeof (struct grub_relocator_chunk));
 
1328
  if (!chunk)
 
1329
    return grub_errno;
 
1330
 
 
1331
  if (malloc_in_range (rel, min_addr, max_addr, align,
 
1332
                       size, chunk,
 
1333
                       preference != GRUB_RELOCATOR_PREFERENCE_HIGH, 1))
 
1334
    {
 
1335
      grub_dprintf ("relocator", "allocated 0x%llx/0x%llx\n",
 
1336
                    (unsigned long long) chunk->src,
 
1337
                    (unsigned long long) chunk->src);
 
1338
      grub_dprintf ("relocator", "chunks = %p\n", rel->chunks);
 
1339
      chunk->target = chunk->src;
 
1340
      chunk->size = size;
 
1341
      chunk->next = rel->chunks;
 
1342
      rel->chunks = chunk;
 
1343
      chunk->srcv = grub_map_memory (chunk->src, chunk->size);
 
1344
      *out = chunk;
 
1345
      return GRUB_ERR_NONE;
 
1346
    }
 
1347
 
 
1348
  adjust_limits (rel, &min_addr2, &max_addr2, min_addr, max_addr);
 
1349
  grub_dprintf ("relocator", "Adjusted limits from %lx-%lx to %lx-%lx\n",
 
1350
                (unsigned long) min_addr, (unsigned long) max_addr,
 
1351
                (unsigned long) min_addr2, (unsigned long) max_addr2);
 
1352
 
 
1353
  do
 
1354
    {
 
1355
      if (malloc_in_range (rel, min_addr2, max_addr2, align,
 
1356
                           size, chunk, 1, 1))
 
1357
        break;
 
1358
 
 
1359
      if (malloc_in_range (rel, rel->highestnonpostaddr, ~(grub_addr_t)0, 1,
 
1360
                           size, chunk, 0, 1))
 
1361
        {
 
1362
          if (rel->postchunks > chunk->src)
 
1363
            rel->postchunks = chunk->src;
 
1364
          break;
 
1365
        }
 
1366
 
 
1367
      return grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
 
1368
    }
 
1369
  while (0);
 
1370
 
 
1371
  {
 
1372
    int found = 0;
 
1373
    auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t,
 
1374
                                    grub_memory_type_t);
 
1375
    int NESTED_FUNC_ATTR hook (grub_uint64_t addr, grub_uint64_t sz,
 
1376
                               grub_memory_type_t type)
 
1377
    {
 
1378
      grub_uint64_t candidate;
 
1379
      if (type != GRUB_MEMORY_AVAILABLE)
 
1380
        return 0;
 
1381
      candidate = ALIGN_UP (addr, align);
 
1382
      if (candidate < min_addr)
 
1383
        candidate = ALIGN_UP (min_addr, align);
 
1384
      if (candidate + size > addr + sz
 
1385
          || candidate > ALIGN_DOWN (max_addr, align))
 
1386
        return 0;
 
1387
      if (preference == GRUB_RELOCATOR_PREFERENCE_HIGH)
 
1388
        candidate = ALIGN_DOWN (min (addr + sz - size, max_addr), align);
 
1389
      if (!found || (preference == GRUB_RELOCATOR_PREFERENCE_HIGH
 
1390
                     && candidate > chunk->target))
 
1391
        chunk->target = candidate;
 
1392
      if (!found || (preference == GRUB_RELOCATOR_PREFERENCE_LOW
 
1393
                     && candidate < chunk->target))
 
1394
        chunk->target = candidate;
 
1395
      found = 1;
 
1396
      return 0;
 
1397
    }
 
1398
 
 
1399
    grub_machine_mmap_iterate (hook);
 
1400
    if (!found)
 
1401
      return grub_error (GRUB_ERR_BAD_OS, "couldn't find suitable memory target");
 
1402
  }
 
1403
  while (1)
 
1404
    {
 
1405
      struct grub_relocator_chunk *chunk2;
 
1406
      for (chunk2 = rel->chunks; chunk2; chunk2 = chunk2->next)
 
1407
        if ((chunk2->target <= chunk->target
 
1408
             && chunk->target < chunk2->target + chunk2->size)
 
1409
            || (chunk2->target <= chunk->target + size
 
1410
                && chunk->target + size < chunk2->target + chunk2->size)
 
1411
            || (chunk->target <= chunk2->target && chunk2->target
 
1412
                < chunk->target + size)
 
1413
            || (chunk->target <= chunk2->target + chunk2->size
 
1414
                && chunk2->target + chunk2->size < chunk->target + size))
 
1415
          {
 
1416
            if (preference == GRUB_RELOCATOR_PREFERENCE_HIGH)
 
1417
              chunk->target = ALIGN_DOWN (chunk2->target, align);
 
1418
            else
 
1419
              chunk->target = ALIGN_UP (chunk2->target + chunk2->size, align);
 
1420
            break;
 
1421
          }
 
1422
      if (!chunk2)
 
1423
        break;
 
1424
    }
 
1425
 
 
1426
  if (chunk->src < chunk->target)
 
1427
    rel->relocators_size += grub_relocator_backward_size;
 
1428
  if (chunk->src > chunk->target)
 
1429
    rel->relocators_size += grub_relocator_forward_size;
 
1430
 
 
1431
  chunk->size = size;
 
1432
  chunk->next = rel->chunks;
 
1433
  rel->chunks = chunk;
 
1434
  grub_dprintf ("relocator", "cur = %p, next = %p\n", rel->chunks,
 
1435
                rel->chunks->next);
 
1436
  chunk->srcv = grub_map_memory (chunk->src, chunk->size);
 
1437
  *out = chunk;
 
1438
#ifdef DEBUG_RELOCATOR
 
1439
  {
 
1440
    grub_mm_region_t r;
 
1441
    grub_mm_header_t p;
 
1442
 
 
1443
    grub_memset (chunk->srcv, 0xfa, chunk->size);
 
1444
    for (r = grub_mm_base; r; r = r->next)
 
1445
      {
 
1446
        p = r->first;
 
1447
        do
 
1448
          {
 
1449
            if ((grub_addr_t) p < (grub_addr_t) (r + 1)
 
1450
                || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
 
1451
              grub_fatal (__FILE__ "%d: out of range pointer: %p\n", __LINE__, p);
 
1452
            p = p->next;
 
1453
          }
 
1454
        while (p != r->first);
 
1455
      }
 
1456
  }
 
1457
#endif
 
1458
  return GRUB_ERR_NONE;
 
1459
}
 
1460
 
 
1461
void
 
1462
grub_relocator_unload (struct grub_relocator *rel)
 
1463
{
 
1464
  struct grub_relocator_chunk *chunk, *next;
 
1465
  if (!rel)
 
1466
    return;
 
1467
  for (chunk = rel->chunks; chunk; chunk = next)
 
1468
    {
 
1469
      unsigned i;
 
1470
      for (i = 0; i < chunk->nsubchunks; i++) 
 
1471
        free_subchunk (&chunk->subchunks[i]);
 
1472
      grub_unmap_memory (chunk->srcv, chunk->size);
 
1473
      next = chunk->next;
 
1474
      grub_free (chunk->subchunks);
 
1475
      grub_free (chunk);
 
1476
    }
 
1477
  grub_free (rel);
 
1478
}
 
1479
 
 
1480
grub_err_t
 
1481
grub_relocator_prepare_relocs (struct grub_relocator *rel, grub_addr_t addr,
 
1482
                               void **relstart, grub_size_t *relsize)
 
1483
{
 
1484
  grub_uint8_t *rels;
 
1485
  grub_uint8_t *rels0;
 
1486
  struct grub_relocator_chunk *sorted;
 
1487
  grub_size_t nchunks = 0;
 
1488
  unsigned j;
 
1489
  struct grub_relocator_chunk movers_chunk;
 
1490
 
 
1491
  grub_dprintf ("relocator", "Preparing relocs (size=%ld)\n",
 
1492
                (unsigned long) rel->relocators_size);
 
1493
 
 
1494
  if (!malloc_in_range (rel, 0, ~(grub_addr_t)0 - rel->relocators_size + 1,
 
1495
                        grub_relocator_align,
 
1496
                        rel->relocators_size, &movers_chunk, 1, 1))
 
1497
    return grub_error (GRUB_ERR_OUT_OF_MEMORY, "out of memory");
 
1498
  movers_chunk.srcv = rels = rels0
 
1499
    = grub_map_memory (movers_chunk.src, movers_chunk.size);
 
1500
 
 
1501
  if (relsize)
 
1502
    *relsize = rel->relocators_size;
 
1503
 
 
1504
  grub_dprintf ("relocator", "Relocs allocated at %p\n", movers_chunk.srcv);
 
1505
  
 
1506
  {
 
1507
    unsigned i;
 
1508
    grub_size_t count[257];
 
1509
    struct grub_relocator_chunk *from, *to, *tmp;
 
1510
 
 
1511
    grub_memset (count, 0, sizeof (count));
 
1512
 
 
1513
    {
 
1514
        struct grub_relocator_chunk *chunk;
 
1515
        for (chunk = rel->chunks; chunk; chunk = chunk->next)
 
1516
          {
 
1517
            grub_dprintf ("relocator", "chunk %p->%p, 0x%lx\n", 
 
1518
                          (void *) chunk->src, (void *) chunk->target,
 
1519
                          (unsigned long) chunk->size);
 
1520
            nchunks++;
 
1521
            count[(chunk->src & 0xff) + 1]++;
 
1522
          }
 
1523
    }
 
1524
    from = grub_malloc (nchunks * sizeof (sorted[0]));
 
1525
    to = grub_malloc (nchunks * sizeof (sorted[0]));
 
1526
    if (!from || !to)
 
1527
      {
 
1528
        grub_free (from);
 
1529
        grub_free (to);
 
1530
        return grub_errno;
 
1531
      }
 
1532
 
 
1533
    for (j = 0; j < 256; j++)
 
1534
      count[j+1] += count[j];
 
1535
 
 
1536
    {
 
1537
      struct grub_relocator_chunk *chunk;
 
1538
      for (chunk = rel->chunks; chunk; chunk = chunk->next)
 
1539
        from[count[chunk->src & 0xff]++] = *chunk;
 
1540
    }
 
1541
 
 
1542
    for (i = 1; i < GRUB_CPU_SIZEOF_VOID_P; i++)
 
1543
      {
 
1544
        grub_memset (count, 0, sizeof (count));
 
1545
        for (j = 0; j < nchunks; j++)
 
1546
          count[((from[j].src >> (8 * i)) & 0xff) + 1]++;
 
1547
        for (j = 0; j < 256; j++)
 
1548
          count[j+1] += count[j];
 
1549
        for (j = 0; j < nchunks; j++)
 
1550
          to[count[(from[j].src >> (8 * i)) & 0xff]++] = from[j];
 
1551
        tmp = to;
 
1552
        to = from;
 
1553
        from = tmp;
 
1554
      }
 
1555
    sorted = from;
 
1556
    grub_free (to);
 
1557
  }
 
1558
 
 
1559
  for (j = 0; j < nchunks; j++)
 
1560
    {
 
1561
      grub_dprintf ("relocator", "sorted chunk %p->%p, 0x%lx\n", 
 
1562
                    (void *) sorted[j].src, (void *) sorted[j].target,
 
1563
                    (unsigned long) sorted[j].size);
 
1564
      if (sorted[j].src < sorted[j].target)
 
1565
        {
 
1566
          grub_cpu_relocator_backward ((void *) rels,
 
1567
                                       sorted[j].srcv,
 
1568
                                       grub_map_memory (sorted[j].target,
 
1569
                                                        sorted[j].size),
 
1570
                                       sorted[j].size);
 
1571
          rels += grub_relocator_backward_size;
 
1572
        }
 
1573
      if (sorted[j].src > sorted[j].target)
 
1574
        {
 
1575
          grub_cpu_relocator_forward ((void *) rels,
 
1576
                                      sorted[j].srcv,
 
1577
                                      grub_map_memory (sorted[j].target,
 
1578
                                                       sorted[j].size),
 
1579
                                      sorted[j].size);
 
1580
          rels += grub_relocator_forward_size;
 
1581
        }
 
1582
      if (sorted[j].src == sorted[j].target)
 
1583
        grub_arch_sync_caches (sorted[j].srcv, sorted[j].size);
 
1584
    }
 
1585
  grub_cpu_relocator_jumper ((void *) rels, (grub_addr_t) addr);
 
1586
  *relstart = rels0;
 
1587
  grub_free (sorted);
 
1588
  return GRUB_ERR_NONE;
 
1589
}
 
1590
 
 
1591
void
 
1592
grub_mm_check_real (char *file, int line)
 
1593
{
 
1594
  grub_mm_region_t r;
 
1595
  grub_mm_header_t p, pa;
 
1596
 
 
1597
  for (r = grub_mm_base; r; r = r->next)
 
1598
    {
 
1599
      pa = r->first;
 
1600
      p = pa->next;
 
1601
      if (p->magic == GRUB_MM_ALLOC_MAGIC)
 
1602
        continue;
 
1603
      do 
 
1604
        {
 
1605
          if ((grub_addr_t) p < (grub_addr_t) (r + 1)
 
1606
              || (grub_addr_t) p >= (grub_addr_t) (r + 1) + r->size)
 
1607
            grub_fatal ("%s:%d: out of range pointer: %p\n", file, line, p);
 
1608
          if (p->magic != GRUB_MM_FREE_MAGIC)
 
1609
            grub_fatal ("%s:%d free magic broken at %p (0x%x)\n", file,
 
1610
                        line, p, p->magic);
 
1611
          pa = p;
 
1612
          p = pa->next;
 
1613
        }
 
1614
      while (pa != r->first);
 
1615
    }
 
1616
}