/* This program illustrates that using a fixed buffer
 * size model to detect potential deadlocks is not sound.
 * Run with nprocs=3.
 *
 * If a 0-buffer-size model is used: f must return 0 on rank 0,
 * therefore g is never called, and there is no deadlock.
 *
 * If a positive-buffer-size model is used: f may return 0 or 1 on
 * rank 0, but g will not deadlock because at least one send will be
 * buffered; again, no deadlock.
 *
 * However in reality the program can deadlock: f() could return 1 on
 * rank 0, and then the sends in g() could be forced to synchronize
 * regardless, leading to deadlock.
 *
 * Author: Stephen Siegel
 */
#define DEBUG
#include <mpi.h>
#include <assert.h>
#include <stdlib.h>
#ifdef DEBUG
#include <stdio.h>
#endif
#define TAG 99
int nprocs, rank;

/* Receive into an int buffer of length count from proc src */
void recv(int * buf, int count, int src) {
  MPI_Status status;
  MPI_Recv(buf, count, MPI_INT, src, TAG, MPI_COMM_WORLD, &status);
#ifdef DEBUG
  printf("Proc %d: received from proc %d:", rank, status.MPI_SOURCE);
  for (int i=0; i<count; i++)
    printf(" %d", buf[i]);
  printf("\n");
#endif
}

/* Send an int buffer of length count to proc dest */
void send(int * buf, int count, int dest) {
#ifdef DEBUG
  printf("Proc %d: sending to proc %d:", rank, dest);
  for (int i=0; i<count; i++)
    printf(" %d", buf[i]);
  printf("\n");
#endif
  MPI_Send(buf, count, MPI_INT, dest, TAG, MPI_COMM_WORLD);
}

/* If all communication is synchronous, rank 0 must return 0.
 * If communication can buffer, rank 0 could return 0 or 1. */
int f() {
  int buf;
  if (rank == 0) {
    recv(&buf, 1, MPI_ANY_SOURCE);
    recv(&buf, 1, MPI_ANY_SOURCE);
    return buf;
  } else if (rank == 1) {
    recv(NULL, 0, 2);
    buf = 0;
    send(&buf, 1, 0);
  } else if (rank == 2) {
    buf = 1;
    send(&buf, 1, 0);
    send(NULL, 0, 1);
  }
  return 0;
}

/* Deadlocks iff all communication is synchronous. */
void g() {
  if (rank == 0) {
    send(NULL, 0, 1);
    recv(NULL, 0, 1);
  } else if (rank == 1) {
    send(NULL, 0, 0);
    recv(NULL, 0, 0);
  }
}

/* May or may not deadlock */
int main(int argc, char * argv[]) {
  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  assert(nprocs >= 3);
  int x = f();
  MPI_Barrier(MPI_COMM_WORLD);
  MPI_Bcast(&x, 1, MPI_INT, 0, MPI_COMM_WORLD);
  if (x) g();
  MPI_Finalize();
}
