d655e628aa1ff5e88626a68d5f7de205b91b532b
[framework/graphics/cairo.git] / src / cairo-xcb-shm.c
1 /* Cairo - a vector graphics library with display and print output
2  *
3  * Copyright © 2007 Chris Wilson
4  * Copyright © 2009 Intel Corporation
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it either under the terms of the GNU Lesser General Public
8  * License version 2.1 as published by the Free Software Foundation
9  * (the "LGPL") or, at your option, under the terms of the Mozilla
10  * Public License Version 1.1 (the "MPL"). If you do not alter this
11  * notice, a recipient may use your version of this file under either
12  * the MPL or the LGPL.
13  *
14  * You should have received a copy of the LGPL along with this library
15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17  * You should have received a copy of the MPL along with this library
18  * in the file COPYING-MPL-1.1
19  *
20  * The contents of this file are subject to the Mozilla Public License
21  * Version 1.1 (the "License"); you may not use this file except in
22  * compliance with the License. You may obtain a copy of the License at
23  * http://www.mozilla.org/MPL/
24  *
25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27  * the specific language governing rights and limitations.
28  *
29  * The Original Code is the cairo graphics library.
30  *
31  * The Initial Developer of the Original Code is Red Hat, Inc.
32  *
33  * Contributors(s):
34  *      Chris Wilson <chris@chris-wilson.co.uk>
35  */
36
37 #include "cairoint.h"
38
39 #if CAIRO_HAS_XCB_SHM_FUNCTIONS
40
41 #include "cairo-xcb-private.h"
42 #include "cairo-list-inline.h"
43
44 #include <xcb/shm.h>
45 #include <sys/ipc.h>
46 #include <sys/shm.h>
47 #include <errno.h>
48
49 #define CAIRO_MAX_SHM_MEMORY (16*1024*1024)
50
51 /* a simple buddy allocator for memory pools
52  * XXX fragmentation? use Doug Lea's malloc?
53  */
54
55 typedef struct _cairo_xcb_shm_mem_block cairo_xcb_shm_mem_block_t;
56
57 typedef enum {
58     PENDING_WAIT,
59     PENDING_POLL
60 } shm_wait_type_t;
61
62 struct _cairo_xcb_shm_mem_block {
63     unsigned int bits;
64     cairo_list_t link;
65 };
66
67 struct _cairo_xcb_shm_mem_pool {
68     int shmid;
69     uint32_t shmseg;
70
71     char *base;
72     unsigned int nBlocks;
73     cairo_xcb_shm_mem_block_t *blocks;
74     cairo_list_t free[32];
75     unsigned char *map;
76
77     unsigned int min_bits;     /* Minimum block size is 1 << min_bits */
78     unsigned int num_sizes;
79
80     size_t free_bytes;
81     size_t max_bytes;
82     unsigned int max_free_bits;
83
84     cairo_list_t link;
85 };
86
87 #define BITTEST(p, n)  ((p)->map[(n) >> 3] &   (128 >> ((n) & 7)))
88 #define BITSET(p, n)   ((p)->map[(n) >> 3] |=  (128 >> ((n) & 7)))
89 #define BITCLEAR(p, n) ((p)->map[(n) >> 3] &= ~(128 >> ((n) & 7)))
90
91 static void
92 clear_bits (cairo_xcb_shm_mem_pool_t *pi, size_t first, size_t last)
93 {
94     size_t i, n = last;
95     size_t first_full = (first + 7) & ~7;
96     size_t past_full = last & ~7;
97     size_t bytes;
98
99     if (n > first_full)
100         n = first_full;
101     for (i = first; i < n; i++)
102           BITCLEAR (pi, i);
103
104     if (past_full > first_full) {
105         bytes = past_full - first_full;
106         bytes = bytes >> 3;
107         memset (pi->map + (first_full >> 3), 0, bytes);
108     }
109
110     if (past_full < n)
111         past_full = n;
112     for (i = past_full; i < last; i++)
113         BITCLEAR (pi, i);
114 }
115
116 static void
117 free_bits (cairo_xcb_shm_mem_pool_t *pi,
118            size_t start,
119            unsigned int bits,
120            cairo_bool_t clear)
121 {
122     cairo_xcb_shm_mem_block_t *block;
123
124     if (clear)
125         clear_bits (pi, start, start + (1 << bits));
126
127     block = pi->blocks + start;
128     block->bits = bits;
129
130     cairo_list_add (&block->link, &pi->free[bits]);
131
132     pi->free_bytes += 1 << (bits + pi->min_bits);
133     if (bits > pi->max_free_bits)
134         pi->max_free_bits = bits;
135 }
136
137 /* Add a chunk to the free list */
138 static void
139 free_blocks (cairo_xcb_shm_mem_pool_t *pi,
140              size_t first,
141              size_t last,
142              cairo_bool_t clear)
143 {
144     size_t i;
145     size_t bits = 0;
146     size_t len = 1;
147
148     i = first;
149     while (i < last) {
150         /* To avoid cost quadratic in the number of different
151          * blocks produced from this chunk of store, we have to
152          * use the size of the previous block produced from this
153          * chunk as the starting point to work out the size of the
154          * next block we can produce. If you look at the binary
155          * representation of the starting points of the blocks
156          * produced, you can see that you first of all increase the
157          * size of the blocks produced up to some maximum as the
158          * address dealt with gets offsets added on which zap out
159          * low order bits, then decrease as the low order bits of the
160          * final block produced get added in. E.g. as you go from
161          * 001 to 0111 you generate blocks
162          * of size 001 at 001 taking you to 010
163          * of size 010 at 010 taking you to 100
164          * of size 010 at 100 taking you to 110
165          * of size 001 at 110 taking you to 111
166          * So the maximum total cost of the loops below this comment
167          * is one trip from the lowest blocksize to the highest and
168          * back again.
169          */
170         while (bits < pi->num_sizes - 1) {
171             size_t next_bits = bits + 1;
172             size_t next_len = len << 1;
173
174             if (i + next_bits > last) {
175                 /* off end of chunk to be freed */
176                 break;
177             }
178
179             if (i & (next_len - 1)) /* block would not be on boundary */
180                 break;
181
182             bits = next_bits;
183             len = next_len;
184         }
185
186         do {
187             if (i + len > last) /* off end of chunk to be freed */
188                 continue;
189
190             if (i & (len - 1)) /* block would not be on boundary */
191                 continue;
192
193             /* OK */
194             break;
195
196             bits--;
197             len >>=1;
198         } while (len > 0);
199
200         if (len == 0)
201             break;
202
203         free_bits (pi, i, bits, clear);
204         i += len;
205     }
206 }
207
208 static cairo_status_t
209 _cairo_xcb_shm_mem_pool_init (cairo_xcb_shm_mem_pool_t *pi,
210                               size_t bytes,
211                               unsigned int min_bits,
212                               unsigned int num_sizes)
213 {
214     size_t setBits;
215     int i;
216
217     assert ((((unsigned long) pi->base) & ((1 << min_bits) - 1)) == 0);
218     assert (num_sizes < ARRAY_LENGTH (pi->free));
219
220     pi->free_bytes = 0;
221     pi->max_bytes = bytes;
222     pi->max_free_bits = 0;
223
224     setBits = bytes >> min_bits;
225     pi->blocks = calloc (setBits, sizeof (cairo_xcb_shm_mem_block_t));
226     if (pi->blocks == NULL)
227         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
228
229     pi->nBlocks = setBits;
230     pi->min_bits = min_bits;
231     pi->num_sizes = num_sizes;
232
233     for (i = 0; i < ARRAY_LENGTH (pi->free); i++)
234         cairo_list_init (&pi->free[i]);
235
236     pi->map = malloc ((setBits + 7) >> 3);
237     if (pi->map == NULL) {
238         free (pi->blocks);
239         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
240     }
241
242     memset (pi->map, -1, (setBits + 7) >> 3);
243     clear_bits (pi, 0, setBits);
244
245     /* Now add all blocks to the free list */
246     free_blocks (pi, 0, setBits, 1);
247
248     return CAIRO_STATUS_SUCCESS;
249 }
250
251 static cairo_xcb_shm_mem_block_t *
252 get_buddy (cairo_xcb_shm_mem_pool_t *pi,
253            size_t offset,
254            unsigned int bits)
255 {
256     cairo_xcb_shm_mem_block_t *block;
257
258     assert (offset + (1 << bits) <= pi->nBlocks);
259
260     if (BITTEST (pi, offset + (1 << bits) - 1))
261         return NULL; /* buddy is allocated */
262
263     block = pi->blocks + offset;
264     if (block->bits != bits)
265         return NULL; /* buddy is partially allocated */
266
267     return block;
268 }
269
270 static void
271 merge_buddies (cairo_xcb_shm_mem_pool_t *pi,
272                cairo_xcb_shm_mem_block_t *block,
273                unsigned int max_bits)
274 {
275     size_t block_offset = block - pi->blocks;
276     unsigned int bits = block->bits;
277
278     while (bits < max_bits - 1) {
279         /* while you can, merge two blocks and get a legal block size */
280         size_t buddy_offset = block_offset ^ (1 << bits);
281
282         block = get_buddy (pi, buddy_offset, bits);
283         if (block == NULL)
284             break;
285
286         cairo_list_del (&block->link);
287
288         /* Merged block starts at buddy */
289         if (buddy_offset < block_offset)
290             block_offset = buddy_offset;
291
292         bits++;
293     }
294
295     block = pi->blocks + block_offset;
296     block->bits = bits;
297     cairo_list_add (&block->link, &pi->free[bits]);
298
299     if (bits > pi->max_free_bits)
300         pi->max_free_bits = bits;
301 }
302
303 /* attempt to merge all available buddies up to a particular size */
304 static unsigned int
305 merge_bits (cairo_xcb_shm_mem_pool_t *pi,
306             unsigned int max_bits)
307 {
308     cairo_xcb_shm_mem_block_t *block, *buddy, *next;
309     unsigned int bits;
310
311     for (bits = 0; bits < max_bits - 1; bits++) {
312         cairo_list_foreach_entry_safe (block, next,
313                                        cairo_xcb_shm_mem_block_t,
314                                        &pi->free[bits],
315                                        link)
316         {
317             size_t buddy_offset = (block - pi->blocks) ^ (1 << bits);
318
319             buddy = get_buddy (pi, buddy_offset, bits);
320             if (buddy == NULL)
321                 continue;
322
323             if (buddy == next) {
324                 next = cairo_container_of (buddy->link.next,
325                                            cairo_xcb_shm_mem_block_t,
326                                            link);
327             }
328
329             cairo_list_del (&block->link);
330             merge_buddies (pi, block, max_bits);
331         }
332     }
333
334     return pi->max_free_bits;
335 }
336
337 /* find store for 1 << bits blocks */
338 static void *
339 buddy_malloc (cairo_xcb_shm_mem_pool_t *pi,
340               unsigned int bits)
341 {
342     unsigned int b;
343     size_t offset;
344     size_t past;
345     cairo_xcb_shm_mem_block_t *block;
346
347     if (bits > pi->max_free_bits && bits > merge_bits (pi, bits))
348         return NULL;
349
350     /* Find a list with blocks big enough on it */
351     block = NULL;
352     for (b = bits; b <= pi->max_free_bits; b++) {
353         if (! cairo_list_is_empty (&pi->free[b])) {
354             block = cairo_list_first_entry (&pi->free[b],
355                                             cairo_xcb_shm_mem_block_t,
356                                             link);
357             break;
358         }
359     }
360     assert (block != NULL);
361
362     cairo_list_del (&block->link);
363
364     while (cairo_list_is_empty (&pi->free[pi->max_free_bits])) {
365         if (--pi->max_free_bits == 0)
366             break;
367     }
368
369     /* Mark end of allocated area */
370     offset = block - pi->blocks;
371     past = offset + (1 << bits);
372     BITSET (pi, past - 1);
373     block->bits = bits;
374
375     /* If we used a larger free block than we needed, free the rest */
376     pi->free_bytes -= 1 << (b + pi->min_bits);
377     free_blocks (pi, past, offset + (1 << b), 0);
378
379     return pi->base + ((block - pi->blocks) << pi->min_bits);
380 }
381
382 static void *
383 _cairo_xcb_shm_mem_pool_malloc (cairo_xcb_shm_mem_pool_t *pi,
384                                 size_t bytes)
385 {
386     unsigned int bits;
387     size_t size;
388
389     size = 1 << pi->min_bits;
390     for (bits = 0; size < bytes; bits++)
391         size <<= 1;
392     if (bits >= pi->num_sizes)
393         return NULL;
394
395     return buddy_malloc (pi, bits);
396 }
397
398 static void
399 _cairo_xcb_shm_mem_pool_free (cairo_xcb_shm_mem_pool_t *pi,
400                               char *storage)
401 {
402     size_t block_offset;
403     cairo_xcb_shm_mem_block_t *block;
404
405     block_offset = (storage - pi->base) >> pi->min_bits;
406     block = pi->blocks + block_offset;
407
408     BITCLEAR (pi, block_offset + ((1 << block->bits) - 1));
409     pi->free_bytes += 1 << (block->bits + pi->min_bits);
410
411     merge_buddies (pi, block, pi->num_sizes);
412 }
413
414 static void
415 _cairo_xcb_shm_mem_pool_destroy (cairo_xcb_shm_mem_pool_t *pool)
416 {
417     shmdt (pool->base);
418     cairo_list_del (&pool->link);
419
420     free (pool->map);
421     free (pool->blocks);
422     free (pool);
423 }
424
425 static void
426 _cairo_xcb_shm_info_finalize (cairo_xcb_shm_info_t *shm_info)
427 {
428     cairo_xcb_connection_t *connection = shm_info->connection;
429
430     assert (CAIRO_MUTEX_IS_LOCKED (connection->shm_mutex));
431
432     _cairo_xcb_shm_mem_pool_free (shm_info->pool, shm_info->mem);
433     _cairo_freepool_free (&connection->shm_info_freelist, shm_info);
434
435     /* scan for old, unused pools - hold at least one in reserve */
436     if (! cairo_list_is_singular (&connection->shm_pools))
437     {
438         cairo_xcb_shm_mem_pool_t *pool, *next;
439         cairo_list_t head;
440
441         cairo_list_init (&head);
442         cairo_list_move (connection->shm_pools.next, &head);
443
444         cairo_list_foreach_entry_safe (pool, next, cairo_xcb_shm_mem_pool_t,
445                                        &connection->shm_pools, link)
446         {
447             if (pool->free_bytes == pool->max_bytes) {
448                 _cairo_xcb_connection_shm_detach (connection, pool->shmseg);
449                 _cairo_xcb_shm_mem_pool_destroy (pool);
450             }
451         }
452
453         cairo_list_move (head.next, &connection->shm_pools);
454     }
455 }
456
457 static void
458 _cairo_xcb_shm_process_pending (cairo_xcb_connection_t *connection, shm_wait_type_t wait)
459 {
460     cairo_xcb_shm_info_t *info, *next;
461     xcb_get_input_focus_reply_t *reply;
462
463     assert (CAIRO_MUTEX_IS_LOCKED (connection->shm_mutex));
464     cairo_list_foreach_entry_safe (info, next, cairo_xcb_shm_info_t,
465                                    &connection->shm_pending, pending)
466     {
467         switch (wait) {
468         case PENDING_WAIT:
469              reply = xcb_wait_for_reply (connection->xcb_connection,
470                                          info->sync.sequence, NULL);
471              break;
472         case PENDING_POLL:
473             if (! xcb_poll_for_reply (connection->xcb_connection,
474                                       info->sync.sequence,
475                                       (void **) &reply, NULL))
476                 /* We cannot be sure the server finished with this image yet, so
477                  * try again later. All other shm info are guaranteed to have a
478                  * larger sequence number and thus don't have to be checked. */
479                 return;
480             break;
481         default:
482             /* silence Clang static analyzer warning */
483             ASSERT_NOT_REACHED;
484             reply = NULL;
485         }
486
487         free (reply);
488         cairo_list_del (&info->pending);
489         _cairo_xcb_shm_info_finalize (info);
490     }
491 }
492
493 cairo_int_status_t
494 _cairo_xcb_connection_allocate_shm_info (cairo_xcb_connection_t *connection,
495                                          size_t size,
496                                          cairo_bool_t might_reuse,
497                                          cairo_xcb_shm_info_t **shm_info_out)
498 {
499     cairo_xcb_shm_info_t *shm_info;
500     cairo_xcb_shm_mem_pool_t *pool, *next;
501     size_t bytes, maxbits = 16, minbits = 8;
502     size_t shm_allocated = 0;
503     void *mem = NULL;
504     cairo_status_t status;
505
506     assert (connection->flags & CAIRO_XCB_HAS_SHM);
507
508     CAIRO_MUTEX_LOCK (connection->shm_mutex);
509     _cairo_xcb_shm_process_pending (connection, PENDING_POLL);
510
511     if (might_reuse) {
512         cairo_list_foreach_entry (shm_info, cairo_xcb_shm_info_t,
513                 &connection->shm_pending, pending) {
514             if (shm_info->size >= size) {
515                 cairo_list_del (&shm_info->pending);
516                 CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
517
518                 xcb_discard_reply (connection->xcb_connection, shm_info->sync.sequence);
519                 shm_info->sync.sequence = XCB_NONE;
520
521                 *shm_info_out = shm_info;
522                 return CAIRO_STATUS_SUCCESS;
523             }
524         }
525     }
526
527     cairo_list_foreach_entry_safe (pool, next, cairo_xcb_shm_mem_pool_t,
528                                    &connection->shm_pools, link)
529     {
530         if (pool->free_bytes > size) {
531             mem = _cairo_xcb_shm_mem_pool_malloc (pool, size);
532             if (mem != NULL) {
533                 /* keep the active pools towards the front */
534                 cairo_list_move (&pool->link, &connection->shm_pools);
535                 goto allocate_shm_info;
536             }
537         }
538         /* scan for old, unused pools */
539         if (pool->free_bytes == pool->max_bytes) {
540             _cairo_xcb_connection_shm_detach (connection,
541                                               pool->shmseg);
542             _cairo_xcb_shm_mem_pool_destroy (pool);
543         } else {
544             shm_allocated += pool->max_bytes;
545         }
546     }
547
548     if (unlikely (shm_allocated >= CAIRO_MAX_SHM_MEMORY)) {
549         CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
550         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
551     }
552
553     pool = malloc (sizeof (cairo_xcb_shm_mem_pool_t));
554     if (unlikely (pool == NULL)) {
555         CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
556         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
557     }
558
559     bytes = 1 << maxbits;
560     while (bytes <= size)
561         bytes <<= 1, maxbits++;
562     bytes <<= 3;
563
564     do {
565         pool->shmid = shmget (IPC_PRIVATE, bytes, IPC_CREAT | 0600);
566         if (pool->shmid != -1)
567             break;
568
569         /* If the allocation failed because we asked for too much memory, we try
570          * again with a smaller request, as long as our allocation still fits. */
571         bytes >>= 1;
572         if (errno != EINVAL || bytes < size)
573             break;
574     } while (TRUE);
575     if (pool->shmid == -1) {
576         int err = errno;
577         if (! (err == EINVAL || err == ENOMEM))
578             connection->flags &= ~CAIRO_XCB_HAS_SHM;
579         free (pool);
580         CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
581         return CAIRO_INT_STATUS_UNSUPPORTED;
582     }
583
584     pool->base = shmat (pool->shmid, NULL, 0);
585     if (unlikely (pool->base == (char *) -1)) {
586         shmctl (pool->shmid, IPC_RMID, NULL);
587         free (pool);
588         CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
589         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
590     }
591
592     status = _cairo_xcb_shm_mem_pool_init (pool,
593                                            bytes,
594                                            minbits,
595                                            maxbits - minbits + 1);
596     if (unlikely (status)) {
597         shmdt (pool->base);
598         free (pool);
599         CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
600         return status;
601     }
602
603     pool->shmseg = _cairo_xcb_connection_shm_attach (connection, pool->shmid, FALSE);
604     shmctl (pool->shmid, IPC_RMID, NULL);
605
606     cairo_list_add (&pool->link, &connection->shm_pools);
607     mem = _cairo_xcb_shm_mem_pool_malloc (pool, size);
608
609   allocate_shm_info:
610     shm_info = _cairo_freepool_alloc (&connection->shm_info_freelist);
611     if (unlikely (shm_info == NULL)) {
612         _cairo_xcb_shm_mem_pool_free (pool, mem);
613         CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
614         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
615     }
616
617     shm_info->connection = connection;
618     shm_info->pool = pool;
619     shm_info->shm = pool->shmseg;
620     shm_info->size = size;
621     shm_info->offset = (char *) mem - (char *) pool->base;
622     shm_info->mem = mem;
623     shm_info->sync.sequence = XCB_NONE;
624
625     /* scan for old, unused pools */
626     cairo_list_foreach_entry_safe (pool, next, cairo_xcb_shm_mem_pool_t,
627                                    &connection->shm_pools, link)
628     {
629         if (pool->free_bytes == pool->max_bytes) {
630             _cairo_xcb_connection_shm_detach (connection,
631                                               pool->shmseg);
632             _cairo_xcb_shm_mem_pool_destroy (pool);
633         }
634     }
635     CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
636
637     *shm_info_out = shm_info;
638     return CAIRO_STATUS_SUCCESS;
639 }
640
641 void
642 _cairo_xcb_shm_info_destroy (cairo_xcb_shm_info_t *shm_info)
643 {
644     cairo_xcb_connection_t *connection = shm_info->connection;
645
646     /* We can only return shm_info->mem to the allocator when we can be sure
647      * that the X server no longer reads from it. Since the X server processes
648      * requests in order, we send a GetInputFocus here.
649      * _cairo_xcb_shm_process_pending () will later check if the reply for that
650      * request was received and then actually mark this memory area as free. */
651
652     CAIRO_MUTEX_LOCK (connection->shm_mutex);
653     assert (shm_info->sync.sequence == XCB_NONE);
654     shm_info->sync = xcb_get_input_focus (connection->xcb_connection);
655
656     cairo_list_init (&shm_info->pending);
657     cairo_list_add_tail (&shm_info->pending, &connection->shm_pending);
658     CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
659 }
660
661 void
662 _cairo_xcb_connection_shm_mem_pools_flush (cairo_xcb_connection_t *connection)
663 {
664     CAIRO_MUTEX_LOCK (connection->shm_mutex);
665     _cairo_xcb_shm_process_pending (connection, PENDING_WAIT);
666     CAIRO_MUTEX_UNLOCK (connection->shm_mutex);
667 }
668
669 void
670 _cairo_xcb_connection_shm_mem_pools_fini (cairo_xcb_connection_t *connection)
671 {
672     assert (cairo_list_is_empty (&connection->shm_pending));
673     while (! cairo_list_is_empty (&connection->shm_pools)) {
674         _cairo_xcb_shm_mem_pool_destroy (cairo_list_first_entry (&connection->shm_pools,
675                                                                  cairo_xcb_shm_mem_pool_t,
676                                                                  link));
677     }
678 }
679
680 #endif /* CAIRO_HAS_XCB_SHM_FUNCTIONS */