Merge lp:~johill-lanl/epics-base/epicsThreadOnce-atomics-based into lp:~epics-core/epics-base/3.15

Proposed by Jeff Hill on 2011-08-31
Status: Rejected
Rejected by: Andrew Johnson on 2013-11-21
Proposed branch: lp:~johill-lanl/epics-base/epicsThreadOnce-atomics-based
Merge into: lp:~epics-core/epics-base/3.15
Prerequisite: lp:~epics-core/epics-base/epicsR3.15-atomics
Diff against target: 435 lines (+132/-166) (has conflicts)
8 files modified
src/libCom/Makefile (+1/-0)
src/libCom/misc/ipAddrToAsciiAsynchronous.cpp (+1/-1)
src/libCom/osi/epicsThread.h (+1/-1)
src/libCom/osi/epicsThreadOnce.cpp (+129/-0)
src/libCom/osi/os/RTEMS/osdThread.c (+0/-32)
src/libCom/osi/os/WIN32/osdThread.c (+0/-35)
src/libCom/osi/os/posix/osdThread.c (+0/-44)
src/libCom/osi/os/vxWorks/osdThread.c (+0/-53)
Text conflict in src/libCom/Makefile
To merge this branch: bzr merge lp:~johill-lanl/epics-base/epicsThreadOnce-atomics-based
Reviewer Review Type Date Requested Status
Andrew Johnson 2011-08-31 Needs Fixing on 2012-06-04
Review via email: mp+73606@code.launchpad.net

This proposal supersedes a proposal from 2011-08-31.

Description of the change

o added new epicsAtomics based, and OS independent, implementation of epicsThreadOnce in epicsThreadOnce.cpp
o changed type of epicsThreadOnceId from epicsThreadId to void *
o fixed once flag isnt initialized with EPICSTHREAD_ONCE_INIT in ipAddrToAsciiAsynchronous.cpp
o removed OS dependent implementations of epicsThreadOnce from {posix, RTEMS, vxWorks, win32}

To post a comment you must log in.
12261. By Jeff Hill on 2011-08-31

fixed spelling in comment

Andrew Johnson (anj) wrote :

Hi Jeff,

The epicsThreadOnce.cpp file has an essential function epicsThreadOnceOnly() which calls cantProceed(), epicsThreadSleep() and errlogPrintf() [the cantProceed() function also calls both of the other two]. Unfortunately both the errlog and generalTime facilities rely on epicsThreadOnce during initialization, thus this implementation could be subject to circular startup problems.

When I try to boot an IOC on vxWorks 6.8 with this code, it hangs silently while executing the C++ static constructors.

If I replace the errlogPrintf() call with std::printf(), after maybe a 10 second delay waiting for the vxWorks munch file to finish loading I get the message "epicsThreadOnce: waiting for another thread to finish calling the once function" which then repeats forever. Here's the stack of the thread loading the munch file:

0x00206b2c ld +0xb4 : usrModuleLoad ()
0x002069e0 usrModuleLoad+0x1c : loadModule ()
0x001da4c0 loadModule +0x24 : loadModuleAt ()
0x001da3d4 loadModuleAt +0xe0 : 0x001da02c ()
0x001da198 loadLibInit +0x21c: cplusLoadFixup ()
0x002141a4 cplusLoadFixup+0x8c : cplusCallCtors ()
0x00143594 cplusCallCtors+0x28 : _GLOBAL__I_iocshPpdbbase ()
0x010b2bc8 _GLOBAL__I_iocshPpdbbase+0x28 : 0x010b2ae8 ()
0x010b2b44 iocshRegister+0x210: iocshRegister ()
0x010b2978 iocshRegister+0x44 : 0x010b0d40 ()
0x010b0d70 gphInitPvt +0x16c: epicsThreadOnce ()
0x010bdfc4 epicsThreadOnce+0xfc : 0x010c59bc (0x8000003c)
0x010c5a44 epicsThreadSleep+0x8c : taskDelay ()

I suspect it may not be possible to fix this in a generic, portable fashion. The current implementations of epicsThreadOnce() are all OS-specific and understand the OS-specific startup requirements. However I'd be happy to test a revised version if you manage to get it working properly on vxWorks.

- Andrew

review: Needs Fixing

Unmerged revisions

12261. By Jeff Hill on 2011-08-31

fixed spelling in comment

12260. By Jeff Hill on 2011-08-31

o moved epicsThreadOnce impl details to anonymous namespace
o fixed recursion sanity test is too agressive
o added some comments

12259. By Jeff Hill on 2011-08-31

o added new epicsAtomics based, and OS independent, implementation of epicsThreadOnce in epicsThreadOnce.cpp
o changed type of epicsThreadOnceId from epicsThreadId to void *
o fixed once flag isnt initialized with EPICSTHREAD_ONCE_INIT in ipAddrToAsciiAsynchronous.cpp
o removed OS dependent implementations of epicsThreadOnce from {posix, RTEMS, vxWorks, win32}

12258. By Jeff Hill <email address hidden> on 2011-08-30

fixed names on redefinition protection macros for vxWorks

12257. By Jeff Hill on 2011-08-30

fixed epics atomic read memory barrier name - old versions of vxWorks

12256. By Jeff Hill on 2011-08-30

fixed word missing from vxWorks specific read and write memory barrier functions

12255. By Jeff Hill <email address hidden> on 2011-08-30

fixed vxWorks name for epicsAtomicTest

12254. By Jeff Hill <email address hidden> on 2011-08-30

fixed wrong return type old vxWorks epicsAtomicUnlock

12253. By Jeff Hill on 2011-08-30

fixed test count

12252. By Jeff Hill on 2011-08-30

fixed vxWorks jumbled ifdef

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'src/libCom/Makefile'
2--- src/libCom/Makefile 2011-08-31 22:40:22 +0000
3+++ src/libCom/Makefile 2011-08-31 22:40:22 +0000
4@@ -256,6 +256,7 @@
5 SRCS += osdEnv.c
6 SRCS += epicsReadline.c
7 SRCS += epicsTempFile.cpp
8+SRCS += epicsThreadOnce.cpp
9 SRCS += epicsStdio.c
10 SRCS += osdStdio.c
11
12
13=== modified file 'src/libCom/misc/ipAddrToAsciiAsynchronous.cpp'
14--- src/libCom/misc/ipAddrToAsciiAsynchronous.cpp 2008-10-21 20:26:48 +0000
15+++ src/libCom/misc/ipAddrToAsciiAsynchronous.cpp 2011-08-31 22:40:22 +0000
16@@ -127,7 +127,7 @@
17 ipAddrToAsciiEnginePrivate * ipAddrToAsciiEnginePrivate :: pEngine = 0;
18 unsigned ipAddrToAsciiEnginePrivate :: numberOfReferences = 0u;
19 bool ipAddrToAsciiEnginePrivate :: shutdownRequest = false;
20-static epicsThreadOnceId ipAddrToAsciiEngineGlobalMutexOnceFlag = 0;
21+static epicsThreadOnceId ipAddrToAsciiEngineGlobalMutexOnceFlag = EPICS_THREAD_ONCE_INIT;
22
23 // the users are not required to supply a show routine
24 // for there transaction callback class
25
26=== modified file 'src/libCom/osi/epicsThread.h'
27--- src/libCom/osi/epicsThread.h 2010-04-26 20:38:11 +0000
28+++ src/libCom/osi/epicsThread.h 2011-08-31 22:40:22 +0000
29@@ -51,7 +51,7 @@
30 /* (epicsThreadId)0 is guaranteed to be an invalid thread id */
31 typedef struct epicsThreadOSD *epicsThreadId;
32
33-typedef epicsThreadId epicsThreadOnceId;
34+typedef void * epicsThreadOnceId;
35 #define EPICS_THREAD_ONCE_INIT 0
36
37 epicsShareFunc void epicsShareAPI epicsThreadOnce(
38
39=== added file 'src/libCom/osi/epicsThreadOnce.cpp'
40--- src/libCom/osi/epicsThreadOnce.cpp 1970-01-01 00:00:00 +0000
41+++ src/libCom/osi/epicsThreadOnce.cpp 2011-08-31 22:40:22 +0000
42@@ -0,0 +1,129 @@
43+
44+/*************************************************************************\
45+* Copyright (c) 2011 LANS LLC, as Operator of
46+* Los Alamos National Laboratory.
47+* Copyright (c) 2011 UChicago Argonne LLC, as Operator of Argonne
48+* National Laboratory.
49+* Copyright (c) 2002 The Regents of the University of California, as
50+* Operator of Los Alamos National Laboratory.
51+* EPICS BASE is distributed subject to a Software License Agreement found
52+* in file LICENSE that is included with this distribution.
53+\*************************************************************************/
54+
55+/*
56+ * Author Jeffrey O. Hill johill@lanl.gov
57+ * Original Authors (before converting to operating system independent code):
58+ * Jeff Hill, Andrew Johnson, Marty Kraimer, Eric Norum
59+ */
60+
61+#include <cstdlib>
62+
63+#define epicsExportSharedSymbols
64+#include "errlog.h"
65+#include "cantProceed.h"
66+#include "epicsThread.h"
67+#include "epicsAtomic.h"
68+#include "epicsAssert.h"
69+
70+namespace {
71+
72+struct ThreadID {
73+public:
74+ ThreadID ();
75+ ThreadID ( epicsThreadId id );
76+ bool operator == ( const ThreadID & ) const;
77+private:
78+ epicsThreadId m_threadId;
79+ ThreadID ( const ThreadID & ); // disabled
80+ ThreadID & operator = ( const ThreadID & ); // disabled
81+};
82+
83+inline ThreadID :: ThreadID ( epicsThreadId id ) :
84+ m_threadId ( id )
85+{
86+}
87+
88+inline ThreadID :: ThreadID () : m_threadId ( 0 )
89+{
90+}
91+
92+inline bool ThreadID :: operator == ( const ThreadID & ctrl ) const
93+{
94+ return ctrl.m_threadId == m_threadId;
95+}
96+
97+static ThreadID done;
98+
99+} // end of namespace anonymous
100+
101+using namespace epics;
102+using namespace atomic;
103+
104+/*
105+ * epicsThreadOnceOnly ()
106+ */
107+static void epicsShareAPI epicsThreadOnceOnly ( epicsThreadOnceId * pId,
108+ void ( * pFunc )( void * ),
109+ void * pArg )
110+{
111+ static const epicsThreadOnceId idStartup = EPICS_THREAD_ONCE_INIT;
112+ ThreadID self ( epicsThreadGetIdSelf () );
113+ epicsThreadOnceId pCurrent = compareAndSwap ( *pId, idStartup, & self );
114+ if ( pCurrent != & done ) {
115+ if ( pCurrent == idStartup ) {
116+ ( *pFunc ) ( pArg );
117+ set ( *pId, & done );
118+ }
119+ else {
120+ {
121+ ThreadID & initID =
122+ * reinterpret_cast < ThreadID * > ( pCurrent );
123+ if ( initID == self ) {
124+ cantProceed( "epicsThreadOnce() once was called "
125+ "recursively from the user's once fuction\n" );
126+ }
127+ }
128+ static const std :: size_t spinDownInit = 1000u;
129+ static const std :: size_t spinCount = 10u;
130+ STATIC_ASSERT ( spinDownInit > spinCount );
131+ static const std :: size_t spinThresh = spinDownInit - spinCount;
132+ std :: size_t spinDown = spinDownInit;
133+ do {
134+ if ( spinDown <= spinThresh ) {
135+ epicsThreadSleep ( epicsThreadSleepQuantum () );
136+ }
137+ if ( spinDown > 0u ) {
138+ spinDown--;
139+ }
140+ else {
141+ errlogPrintf ( "epicsThreadOnce: waiting for another "
142+ "thread to finish calling the once function\n" );
143+ spinDown = spinThresh;
144+ }
145+ pCurrent = get ( *pId );
146+ } while ( pCurrent != & done );
147+ }
148+ }
149+}
150+
151+//
152+// we implement this as a separate function so that it is easy to see
153+// that the performance impact of the primary (most commonly used) path
154+// and that options for inlining this function are available (based on
155+// source code organization)
156+//
157+// performance might be slightly better if this were implemented as an inline
158+// function, but that would pull epicsAtomic.h into epicsThread.h, and on
159+// windows this includes (the lean and mean version of) windows.h, so perhaps
160+// its best to make this an out-of-line function as that type of instantiation
161+// will probably have only a small negative impact on performance
162+//
163+extern "C" void epicsShareAPI epicsThreadOnce ( epicsThreadOnceId * pId,
164+ void ( * pFunc )( void * ),
165+ void * pArg )
166+{
167+ const epicsThreadOnceId pCurrent = get ( *pId );
168+ if ( pCurrent != & done ) {
169+ epicsThreadOnceOnly ( pId, pFunc, pArg );
170+ }
171+}
172
173=== modified file 'src/libCom/osi/os/RTEMS/osdThread.c'
174--- src/libCom/osi/os/RTEMS/osdThread.c 2010-10-05 19:27:37 +0000
175+++ src/libCom/osi/os/RTEMS/osdThread.c 2011-08-31 22:40:22 +0000
176@@ -60,7 +60,6 @@
177 * Support for `once-only' execution
178 */
179 static int initialized = 0;
180-static epicsMutexId onceMutex;
181
182 /*
183 * Just map osi 0 to 99 into RTEMS 199 to 100
184@@ -231,7 +230,6 @@
185 rtems_task_priority old;
186
187 rtems_task_set_priority (RTEMS_SELF, epicsThreadGetOssPriorityValue(99), &old);
188- onceMutex = epicsMutexMustCreate();
189 taskVarMutex = epicsMutexMustCreate ();
190 rtems_task_ident (RTEMS_SELF, 0, &tid);
191 setThreadInfo (tid, "_main_", NULL, NULL);
192@@ -471,36 +469,6 @@
193 }
194
195 /*
196- * Ensure func() is run only once.
197- */
198-void epicsThreadOnce(epicsThreadOnceId *id, void(*func)(void *), void *arg)
199-{
200- #define EPICS_THREAD_ONCE_DONE (epicsThreadId) 1
201-
202- if (!initialized) epicsThreadInit();
203- epicsMutexMustLock(onceMutex);
204- if (*id != EPICS_THREAD_ONCE_DONE) {
205- if (*id == EPICS_THREAD_ONCE_INIT) { /* first call */
206- *id = epicsThreadGetIdSelf(); /* mark active */
207- epicsMutexUnlock(onceMutex);
208- func(arg);
209- epicsMutexMustLock(onceMutex);
210- *id = EPICS_THREAD_ONCE_DONE; /* mark done */
211- } else if (*id == epicsThreadGetIdSelf()) {
212- epicsMutexUnlock(onceMutex);
213- cantProceed("Recursive epicsThreadOnce() initialization\n");
214- } else
215- while (*id != EPICS_THREAD_ONCE_DONE) {
216- /* Another thread is in the above func(arg) call. */
217- epicsMutexUnlock(onceMutex);
218- epicsThreadSleep(epicsThreadSleepQuantum());
219- epicsMutexMustLock(onceMutex);
220- }
221- }
222- epicsMutexUnlock(onceMutex);
223-}
224-
225-/*
226 * Thread private storage implementation based on the vxWorks
227 * implementation by Andrew Johnson APS/ASD.
228 */
229
230=== modified file 'src/libCom/osi/os/WIN32/osdThread.c'
231--- src/libCom/osi/os/WIN32/osdThread.c 2011-02-11 22:33:58 +0000
232+++ src/libCom/osi/os/WIN32/osdThread.c 2011-08-31 22:40:22 +0000
233@@ -1008,41 +1008,6 @@
234 }
235
236 /*
237- * epicsThreadOnce ()
238- */
239-epicsShareFunc void epicsShareAPI epicsThreadOnce (
240- epicsThreadOnceId *id, void (*func)(void *), void *arg )
241-{
242- static struct epicsThreadOSD threadOnceComplete;
243- #define EPICS_THREAD_ONCE_DONE & threadOnceComplete
244- win32ThreadGlobal * pGbl = fetchWin32ThreadGlobal ();
245-
246- assert ( pGbl );
247-
248- EnterCriticalSection ( & pGbl->mutex );
249-
250- if ( *id != EPICS_THREAD_ONCE_DONE ) {
251- if ( *id == EPICS_THREAD_ONCE_INIT ) { /* first call */
252- *id = epicsThreadGetIdSelf(); /* mark active */
253- LeaveCriticalSection ( & pGbl->mutex );
254- func ( arg );
255- EnterCriticalSection ( & pGbl->mutex );
256- *id = EPICS_THREAD_ONCE_DONE; /* mark done */
257- } else if ( *id == epicsThreadGetIdSelf() ) {
258- LeaveCriticalSection ( & pGbl->mutex );
259- cantProceed( "Recursive epicsThreadOnce() initialization\n" );
260- } else
261- while ( *id != EPICS_THREAD_ONCE_DONE ) {
262- /* Another thread is in the above func(arg) call. */
263- LeaveCriticalSection ( & pGbl->mutex );
264- epicsThreadSleep ( epicsThreadSleepQuantum() );
265- EnterCriticalSection ( & pGbl->mutex );
266- }
267- }
268- LeaveCriticalSection ( & pGbl->mutex );
269-}
270-
271-/*
272 * epicsThreadPrivateCreate ()
273 */
274 epicsShareFunc epicsThreadPrivateId epicsShareAPI epicsThreadPrivateCreate ()
275
276=== modified file 'src/libCom/osi/os/posix/osdThread.c'
277--- src/libCom/osi/os/posix/osdThread.c 2010-05-14 22:26:54 +0000
278+++ src/libCom/osi/os/posix/osdThread.c 2011-08-31 22:40:22 +0000
279@@ -76,7 +76,6 @@
280 } epicsThreadOSD;
281
282 static pthread_key_t getpthreadInfo;
283-static pthread_mutex_t onceLock;
284 static pthread_mutex_t listLock;
285 static ELLLIST pthreadList = ELLLIST_INIT;
286 static commonAttr *pcommonAttr = 0;
287@@ -207,8 +206,6 @@
288 int status;
289
290 pthread_key_create(&getpthreadInfo,0);
291- status = pthread_mutex_init(&onceLock,0);
292- checkStatusQuit(status,"pthread_mutex_init","epicsThreadInit");
293 status = pthread_mutex_init(&listLock,0);
294 checkStatusQuit(status,"pthread_mutex_init","epicsThreadInit");
295 pcommonAttr = calloc(1,sizeof(commonAttr));
296@@ -321,47 +318,6 @@
297 #endif /*_POSIX_THREAD_ATTR_STACKSIZE*/
298 }
299
300
301-epicsShareFunc void epicsShareAPI epicsThreadOnce(epicsThreadOnceId *id, void (*func)(void *), void *arg)
302-{
303- static struct epicsThreadOSD threadOnceComplete;
304- #define EPICS_THREAD_ONCE_DONE &threadOnceComplete
305- int status;
306-
307- epicsThreadInit();
308- status = mutexLock(&onceLock);
309- if(status) {
310- fprintf(stderr,"epicsThreadOnce: pthread_mutex_lock returned %s.\n",
311- strerror(status));
312- exit(-1);
313- }
314-
315- if (*id != EPICS_THREAD_ONCE_DONE) {
316- if (*id == EPICS_THREAD_ONCE_INIT) { /* first call */
317- *id = epicsThreadGetIdSelf(); /* mark active */
318- status = pthread_mutex_unlock(&onceLock);
319- checkStatusQuit(status,"pthread_mutex_unlock", "epicsThreadOnce");
320- func(arg);
321- status = mutexLock(&onceLock);
322- checkStatusQuit(status,"pthread_mutex_lock", "epicsThreadOnce");
323- *id = EPICS_THREAD_ONCE_DONE; /* mark done */
324- } else if (*id == epicsThreadGetIdSelf()) {
325- status = pthread_mutex_unlock(&onceLock);
326- checkStatusQuit(status,"pthread_mutex_unlock", "epicsThreadOnce");
327- cantProceed("Recursive epicsThreadOnce() initialization\n");
328- } else
329- while (*id != EPICS_THREAD_ONCE_DONE) {
330- /* Another thread is in the above func(arg) call. */
331- status = pthread_mutex_unlock(&onceLock);
332- checkStatusQuit(status,"pthread_mutex_unlock", "epicsThreadOnce");
333- epicsThreadSleep(epicsThreadSleepQuantum());
334- status = mutexLock(&onceLock);
335- checkStatusQuit(status,"pthread_mutex_lock", "epicsThreadOnce");
336- }
337- }
338- status = pthread_mutex_unlock(&onceLock);
339- checkStatusQuit(status,"pthread_mutex_unlock","epicsThreadOnce");
340-}
341-
342 epicsShareFunc epicsThreadId epicsShareAPI epicsThreadCreate(const char *name,
343 unsigned int priority, unsigned int stackSize,
344 EPICSTHREADFUNC funptr,void *parm)
345
346=== modified file 'src/libCom/osi/os/vxWorks/osdThread.c'
347--- src/libCom/osi/os/vxWorks/osdThread.c 2010-08-11 15:45:17 +0000
348+++ src/libCom/osi/os/vxWorks/osdThread.c 2011-08-31 22:40:22 +0000
349@@ -53,7 +53,6 @@
350 static void **papTSD = 0;
351 static int nepicsThreadPrivate = 0;
352
353-static SEM_ID epicsThreadOnceMutex = 0;
354
355
356 /* Just map osi 0 to 99 into vx 100 to 199 */
357 /* remember that for vxWorks lower number means higher priority */
358@@ -83,19 +82,6 @@
359 }
360 }
361
362-static void epicsThreadInit(void)
363-{
364- static int lock = 0;
365-
366- while(!vxTas(&lock)) taskDelay(1);
367- if(epicsThreadOnceMutex==0) {
368- epicsThreadOnceMutex = semMCreate(
369- SEM_DELETE_SAFE|SEM_INVERSION_SAFE|SEM_Q_PRIORITY);
370- assert(epicsThreadOnceMutex);
371- }
372- lock = 0;
373-}
374-
375 unsigned int epicsThreadGetStackSize (epicsThreadStackSizeClass stackSizeClass)
376 {
377
378@@ -112,43 +98,6 @@
379 return stackSizeTable[stackSizeClass];
380 }
381
382-struct epicsThreadOSD {};
383- /* Strictly speaking this should be a WIND_TCB, but we only need it to
384- * be able to create an epicsThreadId that is guaranteed never to be
385- * the same as any current TID, and since TIDs are pointers this works.
386- */
387-
388-void epicsThreadOnce(epicsThreadOnceId *id, void (*func)(void *), void *arg)
389-{
390- static struct epicsThreadOSD threadOnceComplete;
391- #define EPICS_THREAD_ONCE_DONE &threadOnceComplete
392- int result;
393-
394- epicsThreadInit();
395- result = semTake(epicsThreadOnceMutex, WAIT_FOREVER);
396- assert(result == OK);
397- if (*id != EPICS_THREAD_ONCE_DONE) {
398- if (*id == EPICS_THREAD_ONCE_INIT) { /* first call */
399- *id = epicsThreadGetIdSelf(); /* mark active */
400- semGive(epicsThreadOnceMutex);
401- func(arg);
402- result = semTake(epicsThreadOnceMutex, WAIT_FOREVER);
403- assert(result == OK);
404- *id = EPICS_THREAD_ONCE_DONE; /* mark done */
405- } else if (*id == epicsThreadGetIdSelf()) {
406- semGive(epicsThreadOnceMutex);
407- cantProceed("Recursive epicsThreadOnce() initialization\n");
408- } else
409- while (*id != EPICS_THREAD_ONCE_DONE) {
410- /* Another thread is in the above func(arg) call. */
411- semGive(epicsThreadOnceMutex);
412- epicsThreadSleep(epicsThreadSleepQuantum());
413- result = semTake(epicsThreadOnceMutex, WAIT_FOREVER);
414- assert(result == OK);
415- }
416- }
417- semGive(epicsThreadOnceMutex);
418-}
419
420
421 static void createFunction(EPICSTHREADFUNC func, void *parm)
422 {
423@@ -173,7 +122,6 @@
424 EPICSTHREADFUNC funptr,void *parm)
425 {
426 int tid;
427- if(epicsThreadOnceMutex==0) epicsThreadInit();
428 if(stackSize<100) {
429 errlogPrintf("epicsThreadCreate %s illegal stackSize %d\n",name,stackSize);
430 return(0);
431@@ -343,7 +291,6 @@
432 static int lock = 0;
433 epicsThreadPrivateId id;
434
435- epicsThreadInit();
436 /*lock is necessary because ++nepicsThreadPrivate may not be indivisible*/
437 while(!vxTas(&lock)) taskDelay(1);
438 id = (epicsThreadPrivateId)++nepicsThreadPrivate;

Subscribers

People subscribed via source and target branches