src/rt/rayfifo.c

#ifndef lint
static const char RCSid[] = "$Id: rayfifo.c,v 2.4 2009/12/13 19:13:04 greg Exp $";
#endif
/*
 *  rayfifo.c - parallelize ray queue that respects order
 *
 *  External symbols declared in ray.h
 */

#include "copyright.h"

/*
 *  These routines are essentially an adjunct to raypcalls.c, providing
 *  a convenient means to get first-in/first-out behavior from multiple
 *  processor cores.  The interface is quite simple, with two functions
 *  and a callback, which must be defined by the calling program.  The
 *  hand-off for finished rays is assigned to ray_fifo_out, which takes
 *  a single pointer to the finished ray and returns a non-negative
 *  integer.  If there is an exceptional condition where termination
 *  is desired, a negative value may be returned.
 *
 *  The ray_fifo_in() call takes a ray that has been initialized in
 *  the same manner as for the ray_pqueue() call, i.e., rayorigin()
 *  has been called and the origin, direction and maximum distance
 *  have all been assigned.  However, the ray number will be reset
 *  by ray_fifo_in() according to the number of rays traced since the
 *  last call to ray_fifo_flush().  This final call completes all
 *  pending ray calculations and frees the FIFO buffer.  If any of
 *  the automatic calls to the ray_fifo_out callback return a
 *  negative value, processing stops and -1 is returned.
 *
 *  Note:  The ray passed to ray_fifo_in() may be overwritten
 *  arbitrarily, since it is passed to ray_pqueue().
 */

#include  "ray.h"
#include  <string.h>

#ifndef MAXFIFO
#define MAXFIFO         4096                    /* clear FIFO past this */
#endif

int             (*ray_fifo_out)(RAY *r) = NULL; /* ray output callback */

static RAY      *r_fifo_buf = NULL;             /* circular FIFO out buffer */
static int      r_fifo_len = 0;                 /* allocated FIFO length */
static RNUMBER  r_fifo_start = 1;               /* first awaited ray */
static RNUMBER  r_fifo_end = 1;                 /* one past FIFO last */
static RNUMBER  r_fifo_next = 1;                /* next ray assignment */

#define r_fifo(rn)      (&r_fifo_buf[(rn)&(r_fifo_len-1)])


static void
ray_fifo_growbuf(void)  /* double buffer size (or set to minimum if NULL) */
{
        RAY     *old_buf = r_fifo_buf;
        int     old_len = r_fifo_len;
        int     i;

        if (r_fifo_buf == NULL)
                r_fifo_len = 32;
        else
                r_fifo_len = r_fifo_len*3/2;
                                                /* allocate new */
        r_fifo_buf = (RAY *)calloc(r_fifo_len, sizeof(RAY));
        if (r_fifo_buf == NULL)
                error(SYSTEM, "out of memory in ray_fifo_growbuf");
        if (old_buf == NULL)
                return;
                                                /* copy old & free */
        for (i = r_fifo_start; i < r_fifo_end; i++)
                *r_fifo(i) = old_buf[i&(old_len-1)];

        free(old_buf);
}


static int
ray_fifo_push(          /* send finished ray to output (or queue it) */
        RAY *r
)
{
        int     rv, nsent = 0;

        if (ray_fifo_out == NULL)
                error(INTERNAL, "ray_fifo_out is NULL");
        if ((r->rno < r_fifo_start) | (r->rno >= r_fifo_next))
                error(INTERNAL, "unexpected ray number in ray_fifo_push()");

        if (r->rno > r_fifo_start) {            /* insert into output queue */
                while (r->rno - r_fifo_start >= r_fifo_len)
                        ray_fifo_growbuf();     /* need more space */
                *r_fifo(r->rno) = *r;
                if (r->rno >= r_fifo_end)
                        r_fifo_end = r->rno + 1;
                return(0);
        }
                        /* r->rno == r_fifo_start, so transfer ray(s) */
        do {
                rv = (*ray_fifo_out)(r);
                r->rno = 0;                     /* flag this entry complete */
                if (rv < 0)
                        return(-1);
                nsent += rv;
                if (++r_fifo_start < r_fifo_end)
                        r = r_fifo(r_fifo_start);
                else if (r_fifo_start > r_fifo_end)
                        r_fifo_end = r_fifo_start;
        } while (r->rno == r_fifo_start);

        return(nsent);
}


int
ray_fifo_in(            /* add ray to FIFO */
        RAY     *r
)
{
        static int      incall = 0;             /* prevent recursion */
        int             rv, rval = 0;

        if (incall++)
                error(INTERNAL, "recursive call to ray_fifo_in()");

                                                /* need to reset our FIFO? */
        if ((r_fifo_start >= 1L<<30) | (r_fifo_len > MAXFIFO)) {
                if ((rv = ray_fifo_flush()) < 0)
                        {--incall; return(-1);}
                rval += rv;
        }
                                                /* queue ray */
        r->rno = r_fifo_next++;
        if ((rv = ray_pqueue(r)) < 0)
                {--incall; return(-1);}

        if (!rv)                                /* no result this time? */
                {--incall; return(rval);}
        
        do {                                    /* else send/queue result */
                if ((rv = ray_fifo_push(r)) < 0)
                        {--incall; return(-1);}
                rval += rv;

        } while (ray_presult(r, -1) > 0);       /* empty in-core queue */

        --incall; return(rval);
}


int
ray_fifo_flush(void)    /* flush everything and release buffer */
{
        RAY     myRay;
        int     rv, rval = 0;
                                                /* clear parallel queue */
        while ((rv = ray_presult(&myRay, 0)) > 0 &&
                        (rv = ray_fifo_push(&myRay)) >= 0)
                rval += rv;

        if (rv < 0)                             /* check for exception */
                return(-1);

        if (r_fifo_start != r_fifo_end)
                error(INTERNAL, "could not empty queue in ray_fifo_flush()");

        if (r_fifo_buf != NULL) {
                free(r_fifo_buf);
                r_fifo_buf = NULL; r_fifo_len = 0;
        }
        r_fifo_next = r_fifo_end = r_fifo_start = 1;

        return(rval);
}
Revision:	2.5
Committed:	Thu Apr 26 18:09:55 2018 UTC (7 years, 6 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.4:	+9 -4 lines
Log Message:	Keep FIFO buffer from growing out of control
#	User	Rev	Content
1	greg	2.1	#ifndef lint
2	greg	2.5	static const char RCSid[] = "$Id: rayfifo.c,v 2.4 2009/12/13 19:13:04 greg Exp $";
3	greg	2.1	#endif
4			/*
5			* rayfifo.c - parallelize ray queue that respects order
6			*
7			* External symbols declared in ray.h
8			*/
9
10			#include "copyright.h"
11
12			/*
13			* These routines are essentially an adjunct to raypcalls.c, providing
14			* a convenient means to get first-in/first-out behavior from multiple
15			* processor cores. The interface is quite simple, with two functions
16			* and a callback, which must be defined by the calling program. The
17			* hand-off for finished rays is assigned to ray_fifo_out, which takes
18			* a single pointer to the finished ray and returns a non-negative
19			* integer. If there is an exceptional condition where termination
20			* is desired, a negative value may be returned.
21			*
22			* The ray_fifo_in() call takes a ray that has been initialized in
23	greg	2.4	* the same manner as for the ray_pqueue() call, i.e., rayorigin()
24			* has been called and the origin, direction and maximum distance
25			* have all been assigned. However, the ray number will be reset
26			* by ray_fifo_in() according to the number of rays traced since the
27	greg	2.1	* last call to ray_fifo_flush(). This final call completes all
28			* pending ray calculations and frees the FIFO buffer. If any of
29			* the automatic calls to the ray_fifo_out callback return a
30			* negative value, processing stops and -1 is returned.
31	greg	2.2	*
32			* Note: The ray passed to ray_fifo_in() may be overwritten
33			* arbitrarily, since it is passed to ray_pqueue().
34	greg	2.1	*/
35
36			#include "ray.h"
37			#include <string.h>
38
39	greg	2.5	#ifndef MAXFIFO
40			#define MAXFIFO 4096 /* clear FIFO past this */
41			#endif
42
43	greg	2.1	int (ray_fifo_out)(RAY r) = NULL; /* ray output callback */
44
45			static RAY r_fifo_buf = NULL; / circular FIFO out buffer */
46			static int r_fifo_len = 0; /* allocated FIFO length */
47			static RNUMBER r_fifo_start = 1; /* first awaited ray */
48			static RNUMBER r_fifo_end = 1; /* one past FIFO last */
49	greg	2.3	static RNUMBER r_fifo_next = 1; /* next ray assignment */
50	greg	2.1
51			#define r_fifo(rn) (&r_fifo_buf[(rn)&(r_fifo_len-1)])
52
53
54			static void
55			ray_fifo_growbuf(void) /* double buffer size (or set to minimum if NULL) */
56			{
57			RAY *old_buf = r_fifo_buf;
58			int old_len = r_fifo_len;
59			int i;
60
61			if (r_fifo_buf == NULL)
62	greg	2.5	r_fifo_len = 32;
63	greg	2.1	else
64	greg	2.5	r_fifo_len = r_fifo_len*3/2;
65	greg	2.1	/* allocate new */
66			r_fifo_buf = (RAY *)calloc(r_fifo_len, sizeof(RAY));
67			if (r_fifo_buf == NULL)
68			error(SYSTEM, "out of memory in ray_fifo_growbuf");
69			if (old_buf == NULL)
70			return;
71			/* copy old & free */
72			for (i = r_fifo_start; i < r_fifo_end; i++)
73			*r_fifo(i) = old_buf[i&(old_len-1)];
74
75			free(old_buf);
76			}
77
78
79			static int
80			ray_fifo_push( /* send finished ray to output (or queue it) */
81			RAY *r
82			)
83			{
84			int rv, nsent = 0;
85
86			if (ray_fifo_out == NULL)
87			error(INTERNAL, "ray_fifo_out is NULL");
88	greg	2.3	if ((r->rno < r_fifo_start) \| (r->rno >= r_fifo_next))
89			error(INTERNAL, "unexpected ray number in ray_fifo_push()");
90	greg	2.2
91	greg	2.1	if (r->rno > r_fifo_start) { /* insert into output queue */
92	greg	2.4	while (r->rno - r_fifo_start >= r_fifo_len)
93	greg	2.3	ray_fifo_growbuf(); /* need more space */
94	greg	2.1	r_fifo(r->rno) = r;
95	greg	2.3	if (r->rno >= r_fifo_end)
96			r_fifo_end = r->rno + 1;
97	greg	2.1	return(0);
98			}
99			/* r->rno == r_fifo_start, so transfer ray(s) */
100			do {
101	greg	2.3	rv = (*ray_fifo_out)(r);
102			r->rno = 0; /* flag this entry complete */
103			if (rv < 0)
104	greg	2.1	return(-1);
105			nsent += rv;
106			if (++r_fifo_start < r_fifo_end)
107			r = r_fifo(r_fifo_start);
108	greg	2.3	else if (r_fifo_start > r_fifo_end)
109			r_fifo_end = r_fifo_start;
110	greg	2.1	} while (r->rno == r_fifo_start);
111
112			return(nsent);
113			}
114
115
116			int
117			ray_fifo_in( /* add ray to FIFO */
118			RAY *r
119			)
120			{
121	greg	2.3	static int incall = 0; /* prevent recursion */
122			int rv, rval = 0;
123
124			if (incall++)
125			error(INTERNAL, "recursive call to ray_fifo_in()");
126	greg	2.1
127	greg	2.5	/* need to reset our FIFO? */
128			if ((r_fifo_start >= 1L<<30) \| (r_fifo_len > MAXFIFO)) {
129	greg	2.1	if ((rv = ray_fifo_flush()) < 0)
130	greg	2.3	{--incall; return(-1);}
131	greg	2.1	rval += rv;
132			}
133			/* queue ray */
134	greg	2.3	r->rno = r_fifo_next++;
135	greg	2.1	if ((rv = ray_pqueue(r)) < 0)
136	greg	2.3	{--incall; return(-1);}
137	greg	2.1
138			if (!rv) /* no result this time? */
139	greg	2.3	{--incall; return(rval);}
140	greg	2.2
141			do { /* else send/queue result */
142			if ((rv = ray_fifo_push(r)) < 0)
143	greg	2.3	{--incall; return(-1);}
144	greg	2.2	rval += rv;
145
146			} while (ray_presult(r, -1) > 0); /* empty in-core queue */
147
148	greg	2.3	--incall; return(rval);
149	greg	2.1	}
150
151
152			int
153			ray_fifo_flush(void) /* flush everything and release buffer */
154			{
155			RAY myRay;
156			int rv, rval = 0;
157			/* clear parallel queue */
158			while ((rv = ray_presult(&myRay, 0)) > 0 &&
159			(rv = ray_fifo_push(&myRay)) >= 0)
160			rval += rv;
161
162	greg	2.3	if (rv < 0) /* check for exception */
163	greg	2.1	return(-1);
164
165			if (r_fifo_start != r_fifo_end)
166	greg	2.3	error(INTERNAL, "could not empty queue in ray_fifo_flush()");
167	greg	2.1
168	greg	2.3	if (r_fifo_buf != NULL) {
169			free(r_fifo_buf);
170			r_fifo_buf = NULL; r_fifo_len = 0;
171			}
172			r_fifo_next = r_fifo_end = r_fifo_start = 1;
173	greg	2.1
174			return(rval);
175			}